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.
Return type: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.
Return type:The prime factors of n