Pollard's p-1 algorithm
ID: pollard-s-p-1-algorithm
For an integer to be factored, John Pollard's method chooses an integer coprime to and an exponent divisible by many small prime powers. Compute by modular exponentiation and the Euclidean algorithm. If , it is a proper divisor. If a prime divisor of has , Fermat's little theorem ensures ; success requires some other prime divisor not to divide . Common choices are and . The method exploits a smooth , rather than a small divisor itself.
New to topics? Read the docs here!