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)
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.
rho(n, x1=2, x2=2)¶
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).
Uses trial division to find prime factors of n.
Parameters: n – An integer to factor. Return type: The prime factors of n