# Factorization¶

## Fermat Factorization¶

Fermat’s factorization method is based on the representation of an odd integer as the difference of two squares:

N = a*a-b*b = (a-b)*(a+b)

## Pollard Rho Algorithm¶

Pollard’s rho algorithm is a special-purpose integer factorization algorithm. It was invented by John Pollard in 1975. It is particularly effective for a composite number having a small prime factor.

## Trial Division¶

Trial division is the most laborious but easiest to understand of the integer factorization algorithms. Try to divide a number n by all prime numbers < sqrt(n).