§ 27.18. Methods of Computation: Primes

Referenced by:: Ch.27
Permalink:: http://dlmf.nist.gov/27.18

An overview of methods for precise counting of the number of primes not exceeding an arbitrary integer $x$ is given in Crandall and Pomerance (2005, §3.7). X. Gourdon has calculated $\pi\!\left(10^{{21}}\right)$ using the combinatorial methods of Lagarias et al. (1985) and Deléglise and Rivat (1996); see Gourdon (2000). An analytic approach using a contour integral of the Riemann zeta function (§Ch.25) is discussed in Borwein et al. (2000).

The Sieve of Eratosthenes (Crandall and Pomerance (2005, §3.2)) generates a list of all primes below a given bound. An alternative procedure is the binary quadratic sieve of Atkin and Bernstein (Crandall and Pomerance (2005, p. 170)).

For small values of $n$ , primality is proven by showing that $n$ is not divisible by any prime not exceeding $\sqrt{n}$ .

Two simple algorithms for proving primality require a knowledge of all or part of the factorization of $n-1,n+1$ , or both; see Crandall and Pomerance (2005, §§4.1–4.2). These algorithms are used for testing primality of Mersenne numbers, $2^{n}-1$ , and Fermat numbers, $2^{{2^{n}}}+1$ .

The APR (Adleman-Pomerance-Rumely) algorithm for primality testing is based on Jacobi sums. It runs in time $O\!\left((\mathrm{log}\, n)^{{c\mathrm{log}\,\mathrm{log}\,\mathrm{log}\, n}}\right)$ . Explanations are given in Cohen (1993, §9.1) and Crandall and Pomerance (2005, §4.4). A practical version is described in Bosma and van der Hulst (1990).

The AKS (Agrawal-Kayal-Saxena) algorithm is the first deterministic, polynomial-time, primality test. That is to say, it runs in time $O\!\left((\mathrm{log}n)^{c}\right)$ for some constant $c$ . An explanation is given in Crandall and Pomerance (2005, §4.5).

The ECPP (Elliptic Curve Primality Proving) algorithm handles primes with over 2000 digits. Explanations are given in Cohen (1993, §9.2) and Crandall and Pomerance (2005, §7.6).