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).