§27.19 Methods of Computation: Factorization

Techniques for factorization of integers fall into three general classes: Deterministic algorithms, Type I probabilistic algorithms whose expected running time depends on the size of the smallest prime factor, and Type II probabilistic algorithms whose expected running time depends on the size of the number to be factored.

Deterministic algorithms are slow but are guaranteed to find the factorization within a known period of time. Trial division is one example. Fermat’s algorithm is another; see Bressoud (1989, §5.1).

Type I probabilistic algorithms include the Brent–Pollard rho algorithm (also called Monte Carlo method), the Pollard $p-1$ algorithm, and the Elliptic Curve Method (ecm). Descriptions of these algorithms are given in Crandall and Pomerance (2005, §§5.2, 5.4, and 7.4). As of January 2009 the largest prime factors found by these methods are a 19-digit prime for Brent–Pollard rho, a 58-digit prime for Pollard $p-1$, and a 67-digit prime for ecm.

Type II probabilistic algorithms for factoring $n$ rely on finding a pseudo-random pair of integers $(x,y)$ that satisfy $x^{2}\equiv y^{2}\pmod{n}$. These algorithms include the Continued Fraction Algorithm (cfrac), the Multiple Polynomial Quadratic Sieve (mpqs), the General Number Field Sieve (gnfs), and the Special Number Field Sieve (snfs). A description of cfrac is given in Bressoud and Wagon (2000). Descriptions of mpqs, gnfs, and snfs are given in Crandall and Pomerance (2005, §§6.1 and 6.2). As of January 2009 the snfs holds the record for the largest integer that has been factored by a Type II probabilistic algorithm, a 307-digit composite integer. The snfs can be applied only to numbers that are very close to a power of a very small base. The largest composite numbers that have been factored by other Type II probabilistic algorithms are a 63-digit integer by cfrac, a 135-digit integer by mpqs, and a 182-digit integer by gnfs.

For further information see Crandall and Pomerance (2005) and §26.22.

For current records see Cunningham Project.