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

`algorithms.factorization.fermat.``fermat`(n)[source]

Factorization of the integer n.

Parameters: n – An integer to be factored. The factorization of n.

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

`algorithms.factorization.pollard_rho.``f`(x)[source]
`algorithms.factorization.pollard_rho.``pollard_rho`(x)[source]
`algorithms.factorization.pollard_rho.``pollard_rho_rec`(x, factors)[source]
`algorithms.factorization.pollard_rho.``rho`(n, x1=2, x2=2)[source]

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

`algorithms.factorization.trial_division.``trial_division`(n)[source]

Uses trial division to find prime factors of n.

Parameters: n – An integer to factor. The prime factors of n