Name
Abstract | ||
|---|---|---|
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 primalitytest algorithms for implementing the Wilson's method, which need 2*[(n-1/2)!] and n(log(2) n)(2)multiplications, respectively. However, by using the proposed reduction algorithm, only n+1/2*[1-(1/2)(k)]+1multiplications are needed for the Wilson's primality test method, where k=[log n-1/2] and the "n" means aprime 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. |
Year | Venue | Keywords |
|---|---|---|
2009 | INFORMATICA-JOURNAL OF COMPUTING AND INFORMATICS | information security, cryptography, modular arithmetic, primality test, number theory |
Field | DocType | Volume |
Miller–Rabin primality test,Discrete mathematics,Provable prime,Primality test,Computer science,Primality certificate,Arithmetic,Industrial-grade prime,Lucas primality test,Solovay–Strassen primality test,Integer factorization | Journal | 33 |
Issue | ISSN | Citations |
4 | 0350-5596 | 0 |
PageRank | References | Authors |
0.34 | 14 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chia-Long Wu | 1 | 68 | 9.36 |
| Der-Chyuan Lou | 2 | 468 | 37.88 |
| Te-Jen Chang | 3 | 47 | 5.72 |