More number-theoretic computations

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:

- Integer multiplication can be done in essentially linear time (1963 Toom). Similar comments apply to division (1966 Cook) and gcd (1971 Knuth). Some authors used slower subroutines for arithmetic (because they were writing before the 1960s, for example); in this table, however, all algorithms use essentially-linear-time subroutines.
- One can quickly find all divisors of n congruent to r modulo m, when m is larger than roughly n^(1/4) (1998 Coppersmith Howgrave-Graham; n^(1/3) for r=1: 1975 Brillhart Lehmer Selfridge; n^(1/3) for arbitrary r: 1984 Lenstra; n^(3/10) for r=1: 1997 Konyagin Pomerance). Some authors use higher-exponent subroutines; in this table, however, all algorithms take advantage of the n^(1/4) subroutine when necessary.

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

- p if they prove primality;
- c if they prove compositeness;
- ? if certificates are merely conjectured to be found for every n;
- r if certificates are provably found for every n, but the algorithm uses randomness; and
- d if certificates are provably deterministically found for every n.

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 |