Comparing and Reviewing Modern Primality Tests
DOI:
https://doi.org/10.47611/jsrhs.v11i3.3860Keywords:
Mathematics, Algorithms, Primality Test, Prime Numbers, Number Theory, Cryptography, Quantum Computing, ECPP, AKS, Fermat, RSA, Encryption, Public Key Cryptography, APR-CL, Pseudoprimes, Carmichael NumbersAbstract
Primality tests refer to algorithms that determine whether a number is prime or composite. These tests are essential to modern encryption algorithms, including the widely used RSA public key encryption algorithm. However, with so many different primality tests out there, choosing the correct one for a given application can be challenging. This paper provides an overview of modern primality tests, detailing the differences between different types of tests and when one test may be preferable to another. Furthermore, implementations of popular primality tests are written and compared to one another graphically to better understand their differing performances. Lastly, we look at next steps for the field of primality tests due to the rise of quantum computing, which could serve as a means of creating even better primality tests.
Downloads
References or Bibliography
Agrawal, M., Kayal, N., & Saxena, N. (2004). Primes is in p. *Annals of Mathematics*, *160*(2), 781–793. https://doi.org/10.4007/annals.2004.160.781
Atkin, A. O., & Morain, F. (1993). Elliptic curves and primality proving. *Mathematics of Computation*, *61*(203), 29–68. https://doi.org/10.1090/s0025-5718-1993-1199989-x
Baillie, R., & Wagstaff, S. S. (1980). Lucas pseudoprimes. *Mathematics of Computation*, *35*(152), 1391–1417. https://doi.org/10.1090/s0025-5718-1980-0583518-6
Bernhardt, C. (2020). *Quantum computing for everyone*. The MIT Press.
Chau, H. F., & Lo, H.-K. (1997). Primality test via quantum factorization. *International Journal of Modern Physics C*, *08*(02), 131–138. https://doi.org/10.1142/s0129183197000138
Damgard, I., Landrock, P., & Pomerance, C. (1993). Average case error estimates for the strong probable prime test. *Mathematics of Computation*, *61*(203), 177. https://doi.org/10.2307/2152945
Damgård, I. B., & Frandsen, G. S. (2003). An extended quadratic frobenius primality test with average and worst case error estimates. *Fundamentals of Computation Theory*, 118–131. https://doi.org/10.1007/978-3-540-45077-1_12
Grantham, J. (1998). A probable prime test with high confidence. *Journal of Number Theory*, *72*(1), 32–47. https://doi.org/10.1006/jnth.1998.2247
Ishmukhametov, S. T., Rubtsova, R., & Savelyev, N. (2018). The error probability of the Miller–Rabin Primality test. *Lobachevskii Journal of Mathematics*, *39*(7), 1010–1015. https://doi.org/10.1134/s1995080218070132
Lenstra, Jr., H., & Pomerance, C. (2019). Primality testing with gaussian periods. *Journal of the European Mathematical Society*, *21*(4), 1229–1269. https://doi.org/10.4171/jems/861
Rabin, M. O. (1980). Probabilistic algorithm for testing primality. *Journal of Number Theory*, *12*(1), 128–138. https://doi.org/10.1016/0022-314x(80)90084-0
Rajput, J., & Bajpai, A. (2019). Study on deterministic and probabilistic computation of primality test. *SSRN Electronic Journal*. https://doi.org/10.2139/ssrn.3358737
Schoof, R. (2008). Four primality testing algorithms. *ArXiv*. https://doi.org/10.48550/ARXIV.0801.3840
Shor, P. W. (1994). Algorithms for quantum computation: Discrete logarithms and factoring. *Proceedings 35th Annual Symposium on Foundations of Computer Science*. https://doi.org/10.1109/sfcs.1994.365700
Published
How to Cite
Issue
Section
Copyright (c) 2022 Ishaan Ganti
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright holder(s) granted JSR a perpetual, non-exclusive license to distriute & display this article.
