A primality test is a test to determine whether or not a given number is prime, as opposed to actually decomposing the number into its constituent prime factors (which is known as prime factorization).

Primality tests come in two varieties: deterministic and probabilistic. Deterministic tests determine with absolute certainty whether a number is prime. Examples of deterministic tests include the Lucas-Lehmer test and elliptic curve primality proving. Probabilistic tests can potentially (although with very small probability) falsely identify a composite number as prime (although not vice versa). However, they are in general much faster than deterministic tests. Numbers that have passed a probabilistic prime test are therefore properly referred to as probable primes until their primality can be demonstrated deterministically.

For an odd integer , classical primality tests can use known prime factors of or , together with suitable modular conditions, to prove that is prime. A complete prime factorization of or is not always necessary. Examples include Pocklington's theorem and the methods of Brillhart et al. (1975), which can also combine information from both and .

A number that passes a probabilistic test but is in fact composite is known as a pseudoprime. There are many specific types of pseudoprimes, the most common being the Fermat pseudoprimes, which are composites that nonetheless satisfy Fermat's little theorem.

The Rabin-Miller strong pseudoprime test is a particularly efficient test. The Wolfram Language implements the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test as the primality test used by the function PrimeQ[n]. Like many such algorithms, it is a probabilistic test using pseudoprimes. In order to guarantee primality, a much slower deterministic algorithm must be used. As of Oct. 2026, no composite number is known to pass the Baillie-PSW primality test.

The state of the art in deterministic primality testing for arbitrary numbers is elliptic curve primality proving. As of Oct. 2026, the largest number certified by the program PRIMO is the repunit prime , with 49,081 decimal digits. Its certification by P. Underwood in 2022 took 20 months on a 64-core AMD Ryzen Threadripper 3990X (Martin).

Unlike prime factorization, primality testing was long believed to be a P-problem (Wagon 1991). This had not been demonstrated, however, until Agrawal et al. (2002) unexpectedly discovered a polynomial time algorithm for primality testing that has asymptotic complexity of (Bernstein 2002, Clark 2002, Indian Institute of Technology 2002, Pomerance 2002ab, Robinson 2002). Their algorithm has come to be called the AKS primality test.

See also

Adleman-Pomerance-Rumely Primality Test, AKS Primality Test, Elliptic Curve Primality Proving, Fermat Pseudoprime, Fermat's Little Theorem, Fermat's Little Theorem Converse, Fermat's Theorem, Lucas-Lehmer Test, Miller's Primality Test, Pépin's Test, Pocklington's Theorem, Prime Factorization Algorithms, Probable Prime, Proth's Theorem, Pseudoprime, Rabin-Miller Strong Pseudoprime Test, Ward's Primality Test, Wilson's Theorem

Explore with Wolfram|Alpha

References

Agrawal, M.; Kayal, N.; and Saxena, N. "PRIMES is in P." Ann. Math. 160, 781-793, 2004. https://doi.org/10.4007/annals.2004.160.781.Beauchemin, P.; Brassard, G.; Crépeau, C.; Goutier, C.; and Pomerance, C. "The Generation of Random Numbers That Are Probably Prime." J. Crypt. 1, 53-64, 1988.Bernstein, D. J. "An Exposition of the Agrawal-Kayal-Saxena Primality-Proving Theorem." 2002. https://cr.yp.to/papers/aks-20020820.pdf.Brillhart, J.; Lehmer, D. H.; and Selfridge, J. L. "New Primality Criteria and Factorizations of ." Math. Comput. 29, 620-647, 1975. https://doi.org/10.1090/S0025-5718-1975-0384673-1.Brillhart, J.; Lehmer, D. H.; Selfridge, J.; Wagstaff, S. S. Jr.; and Tuckerman, B. Factorizations of bⁿ±1, b=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, rev. ed. Providence, RI: Amer. Math. Soc., pp. lviii-lxv, 1988.Clark, E. "Polynomial Time Primality Test." sci.math newsgroup posting. 6 Aug 2002.Cohen, H. and Lenstra, A. K. "Primality Testing and Jacobi Sums." Math. Comput. 42, 297-330, 1984.Indian Institute of Technology. "PRIMES is in P." http://www.cse.iitk.ac.in/news/primality.html.Kayal, N. and Saxena, N. "Towards a Deterministic Polynomial-Time Test." Technical Report. Kanpur, India: Indian Institute of Technology, 2002. https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf.Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998.Martin, M. "PRIMO--Primality Proving." https://www.ellipsa.eu/public/primo/primo.html.Martin, M. "PRIMO Record." https://www.ellipsa.eu/public/primo/records.html.Pomerance, C. "RE: New Polynomial Time Primality Test?" 7 Aug 2002a. https://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0208&L=nmbrthry&P=956.Pomerance, C. "A New Primal Screen." FOCUS: Newsletter of the Math. Assoc. Amer. 22, No. 8, 4-5, 2002b.Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, 1994.Robinson, S. "New Method Said to Solve Key Problem in Math." New York Times, p. A16, August 8, 2002.Wagon, S. "Primality Testing." Math. Intell. 8, No. 3, 58-61, 1986.Wagon, S. Mathematica in Action. New York: W. H. Freeman, pp. 15-17, 1991.Weisstein, E. W. "Primality Testing Is Easy." MathWorld Headline News, Aug. 7, 2002. https://mathworld.wolfram.com/news/2002-08-07/primetest/.Williams, H. C. Edouard Lucas and Primality Testing. New York: Wiley, 1998.

Referenced on Wolfram|Alpha

Primality Test

Cite this as:

Weisstein, Eric W. "Primality Test." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PrimalityTest.html

Subject classifications