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 
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 , and a 67-digit
prime for ecm.
Type II probabilistic algorithms for factoring 
rely on finding a
pseudo-random pair of integers 
that satisfy 
.
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.
