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.
Articles by others on the same topic
There are currently no matching articles.