Comparing and Reviewing Modern Primality Tests

Authors

  • Ishaan Ganti Dr. Ethan Hutt of UNC Chapel Hill

DOI:

https://doi.org/10.47611/jsrhs.v11i3.3860

Keywords:

Mathematics, Algorithms, Primality Test, Prime Numbers, Number Theory, Cryptography, Quantum Computing, ECPP, AKS, Fermat, RSA, Encryption, Public Key Cryptography, APR-CL, Pseudoprimes, Carmichael Numbers

Abstract

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

Download data is not yet available.

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

08-31-2022

How to Cite

Ganti, I. (2022). Comparing and Reviewing Modern Primality Tests. Journal of Student Research, 11(3). https://doi.org/10.47611/jsrhs.v11i3.3860

Issue

Section

HS Research Projects