The following table compares various algorithms for distinguishing prime numbers from composite numbers. Time is measured on conventional von Neumann computers, such as 2-tape Turing machines. Two notes on subroutines:
This table does not list the space used to find, communicate, or verify a certificate.
| Method | Effect of certificate | Certificate exists for | Time to verify certificate | Time to find certificate |
|---|---|---|---|---|
| proving compositeness with factorization: if b divides n and 1<b<n then n is composite | proves compositeness | every composite n | (lg n)^{1+o(1)} | very slow; but (lg n)^{O(1)} for most n |
| proving compositeness with Fermat: if n is not a b-prp, i.e., does not divide b^n-b, then n is composite | proves compositeness | nearly every composite n; however, there are infinitely many composites n that are all-b-prp (1994 Alford Granville Pomerance) | (lg n)^{2+o(1)} | random (lg n)^{2+o(1)} |
| if n is not a b-sprp, i.e., does not divide any of the most obvious factors of b^n-b, then n is composite (1966 Artjuhov) | proves compositeness | every composite n | (lg n)^{2+o(1)} | random (lg n)^{2+o(1)} (1976 Rabin, independently 1980 Monier, independently 1982 Atkin Larson; inferior variant: 1976 Lehmer, independently 1977 Solovay Strassen; other variants: 1998 Grantham, 2001 Grantham, 2001 Mueller, 2003 Damgard Frandsen) |
| conjecturally testing primality: if n is a b-sprp for every prime number b between 1 and (ceil(lg n))^2, then n seems to be prime (basic idea: 1975 Miller) | conjecturally certifies primality; conjecture follows from GRH (1984 Bach; 35(ceil(lg n))^2 announced in 1979 Oesterle; O(ceil(lg n))^2, without explicit O constant: 1952 Ankeny, 1964 Wang, 1971 Montgomery, 1978 Velu) | every prime n | (lg n)^{4+o(1)} | instant |
| if n is a b-sprp for the first 2 ceil(lg n) prime numbers b, then n seems to be prime (folklore; simpler variant giving prime power: 1995 Lukes Patterson Williams) | conjecturally certifies primality | every prime n | (lg n)^{3+o(1)} | instant |
| if n is a 2-sprp and passes a similar quadratic test, then n seems to be prime (1980 Baillie Wagstaff, 1980 Pomerance Selfridge Wagstaff) | conjecturally certifies primality; conjecture is implausible for very large n (1984 Pomerance), but no counterexamples are known | every prime n | (lg n)^{2+o(1)} | instant |
| proving primality with unit-group factors: if b^(n-1)=1 in Z/n, and b^((n-1)/q)-1 is nonzero in Z/n for every prime divisor q of n-1, then n is prime (1876 Lucas, except that the switch from ``divisor q>1'' to ``prime divisor q'' is from 1927 Lehmer by analogy to 1914 Pocklington) | proves primality | every prime n | at most (lg n)^{3+o(1)}; usually (lg n)^{2+o(1)} | very slow; but conjectured to be (lg n)^{O(1)} for infinitely many n |
| if b^(n-1)=1 in Z/n, F is a divisor of n-1, and b^((n-1)/q)-1 is a unit in Z/n for every prime divisor q of F, then every divisor of n is in {1,F+1,2F+1,...}, so if (F+1)^2>n then n is prime (1914 Pocklington); similar test for F down to roughly n^(1/4) | proves primality | every prime n | at most (lg n)^{3+o(1)}; usually (lg n)^{2+o(1)} | very slow; but fast for more n's than above; (lg n)^{O(1)} for infinitely many n (1989 Pintz Steiger Szemeredi; variant: 1992 Fellows Koblitz; another variant: 1997 Konyagin Pomerance) |
| Pocklington-type test with quadratic extensions of Z/n (1876 Lucas, 1930 Lehmer, 1975 Morrison, 1975 Selfridge Wunderlich, 1975 Brillhart Lehmer Selfridge) | proves primality | every prime n | at most (lg n)^{3+o(1)}; usually (lg n)^{2+o(1)} | very slow; but fast for more n's than above |
| Pocklington-type test with higher-degree extensions of Z/n (degrees 4 and 6: 1976 Williams Judd; general degrees: 1983 Adleman Pomerance Rumely) | proves primality | every prime n | (lg n)^{O(lg lg lg n)}, using distribution of divisors of n^d-1 (1983 Adleman Pomerance Rumely, credited to Odlyzko Pomerance; weaker bound: 1955 Prachar; best known bound: 2000 Pelikan Pintz Szemeredi); many speedups available (1978 Williams Holte, 1984 Cohen Lenstra, 1987 Cohen Lenstra, 1990 Bosma van der Hulst, 1997 Mihailescu) | instant |
| proving primality with elliptic-curve factors: similar test using elliptic curves (1986 Goldwasser Kilian) | proves primality, using bounds on elliptic-curve sizes (1936 Hasse) | nearly every prime n; conjecturally, every prime n | (lg n)^{3+o(1)} | (lg n)^{O(1)}, using polynomial-time elliptic-curve point counting (1985 Schoof); many speedups available (1990 Atkin, 1992 Elkies, 1995 Morain) |
| similar test with elliptic curves having order divisible by a large power of 2 (1987 Pomerance) | proves primality, using bounds on elliptic-curve sizes (1936 Hasse) | every prime n | (lg n)^{2+o(1)} | very slow |
| similar test with Jacobians of genus-2 hyperelliptic curves (1992 Adleman Huang) | proves primality, using bounds on Jacobian sizes (1940? Weil) | every prime n | at most (lg n)^{3+o(1)} | random (lg n)^{O(1)}, using distribution of primes in interval of width x^(3/4) around x (1979 Iwaniec Jutila), and distribution of Jacobian sizes |
| similar test with small-discriminant complex-mult elliptic curves (1986? Atkin; special cases: 1985 Bosma, 1986 Chudnovsky Chudnovsky) | proves primality, using bounds on elliptic-curve sizes (1936 Hasse) | conjecturally, every prime n | at most (lg n)^{3+o(1)} | at most (lg n)^{5+o(1)} |
| similar test with small-discriminant complex-mult elliptic curves, merging square-root computations for many discriminants (1990 Lenstra Lenstra, credited to Shallit) | proves primality, using bounds on elliptic-curve sizes (1936 Hasse) | conjecturally, every prime n | at most (lg n)^{3+o(1)} | at most (lg n)^{4+o(1)}; many speedups available (1989 Kaltofen Valente Yui, 1990 Morain, 1993 Atkin Morain, 1998 Morain) |
| proving primality with combinatorics: if we can write down many elements of a particular subgroup of a prime cyclotomic extension of Z/n then n is a power of a prime (2002.08 Agrawal Kayal Saxena) | proves primality | every prime n | (lg n)^{O(1)}, using analytic fact that, for some c>1/2, many primes r have prime divisor of r-1 above r^c (1969 Goldfeld); at most (lg n)^{12+o(1)}, using analytic fact that many primes r have prime divisor of r-1 above r^(2/3) (1985 Fouvry); conjecturally (lg n)^(6+o(1)); many speedups available | instant |
| variant using arbitrary cyclotomic extensions (2002.08 Lenstra) | proves primality | every prime n | at most (lg n)^{12+o(1)}, using crude bound on distribution of primes (1850 Chebyshev); at most (lg n)^{8+o(1)}, using analytic facts as above; conjecturally (lg n)^(6+o(1)) | instant |
| variant using cyclotomic extensions with better bound on group structure (2002.12 Macaj, independently Agrawal) | proves primality | every prime n | at most (lg n)^{10.5+o(1)}, using crude bound on distribution of primes (1850 Chebyshev); at most (lg n)^{7.5+o(1)}, using analytic facts as above; conjecturally (lg n)^(6+o(1)) | instant |
| variant using random Kummer extensions (2003.01 Bernstein; idea and 2-power-degree case: 2002.11 Berrizbeitia; prime-degree case: 2003.01 Cheng) | proves primality | every prime n | (lg n)^{4+o(1)}, using distribution of divisors of n^d-1 (overkill: Odlyzko Pomerance) | random (lg n)^{2+o(1)} |
| variant using Gaussian periods (2003.03 Lenstra Pomerance) | proves primality | every prime n | (lg n)^{6+o(1)}, using various analytic facts | instant |
| if n fails any of the Fermat-type tests in these methods then n is composite | proves compositeness | every composite n | at most (lg n)^{4+o(1)}, using analytic facts as above | at most (lg n)^{6+o(1)}, using analytic facts as above |
The following chart lists compositeness-proving and primality-proving algorithms in order of exponent. Numbers down the side are proven upper bounds for exponents in times to deterministically verify certificates. (Randomness does not help any of the known verification algorithms.) Numbers across the top are proven upper bounds for exponents in times to find certificates. Algorithms are labelled as
| 0+o(1) | 1+o(1) | 2+o(1) | 3+o(1) | 4+o(1) | 5+o(1) | O(1) | very big | |
|---|---|---|---|---|---|---|---|---|
| 1+o(1) | dc | |||||||
| 2+o(1) | rc 1966 | dp 1987 | ||||||
| 3+o(1) | ?p 1990 | ?p 1986 | ?p 1986; rp 1992 |
dp 1914 | ||||
| 4+o(1) | rp 2003 | dc 2003 | ||||||
| 5+o(1) | ||||||||
| 6+o(1) | ?pc 2002; dpc 2003 |
|||||||
| O(1) | dpc 2002 | |||||||
| O(lg lg lg n) | dpc 1979 |