27 Functions of Number TheoryComputation27.18 Methods of Computation: Primes27.20 Methods of Computation: Other Number-Theoretic Functions

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}\phantom{\rule{veryverythickmathspace}{0ex}}(modn)$.
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 current records see Cunningham Project.