Computational reduction of wilson's primality test for modern cryptosystems

In this paper, a method of diminishing computational reduction to improve Wilson's primality test method is proposed. Basically, the RSA algorithm entails a modular exponentiation operation on large integers, which is considerably time-consuming to implement. Since ancient time, number theory has been an important study subject and modular arithmetic has also been widely used in cryptography. The Wilson's primality test method is one of the most well-known deterministic prime number test methods. It states that n is a prime number if and only if (n-1)!≡--1mod n . In this paper, we compare two primality test algorithms for implementing the Wilson's method, which need 1 2*[(n-1/2)!] and n(log₂ n)² multiplications, respectively. However, by using the proposed reduction algorithm, only n+1/2 *[1-(1/2)^k]+1 multiplications are needed for the Wilson's primality test method, where K=[log₂n-1/2] and the "n" means a prime number. The proposed computational reduction method can efficiently perform Wilson's deterministic primality test, and it is faster than other proposed methods. By using the proposed method, it can not only reduce the overall computational complexity of the original Wilson's primality test method but also reduce the computational space.