27 Functions of Number TheoryComputation27.17 Other Applications27.19 Methods of Computation: Factorization

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). T. Oliveira e Silva has calculated $\pi \left(x\right)$ for $x={10}^{23}$, using the combinatorial methods of Lagarias et al. (1985) and Deléglise and Rivat (1996); see Oliveira e Silva (2006). An analytic approach using a contour integral of the Riemann zeta function (§25.2(i)) 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{ln}n)}^{c\mathrm{ln}\mathrm{ln}\mathrm{ln}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{ln}n)}^{c}\right)$ for some constant $c$. An explanation is given in Crandall and Pomerance (2005, §4.5).