Pollard’s $p1$ algorithm
Pollard’s $p\mathrm{}\mathrm{1}$ method is an integer factorization algorithm^{} devised by John Pollard in 1974 to take advantage of Fermat’s little theorem^{}. Theoretically, trial division^{} always returns a result (though of course in practice the computing engine’s resources could be exhausted or the user might not to be around to care for the result). Pollard’s $p1$ algorithm, on the other hand, was designed from the outset to cope with the possibility of failure to return a result.
Choose a test cap $B$ and call Pollard’s $p1$ algorithm with a positive integer.

1.
Use a simple method (such as the sieve of Eratosthenes^{}) to find primes $$, or even probable primes^{}.
 2.

3.
Find the exponent $e$ such that ${p}^{e}\le B$. Then for each $$, compute $b={a}^{{p}^{e}}modn$ and see if $$. If that’s the case, return those results of the greatest common divisor^{} function, exit.

4.
If the GCD function consistently returned 1s, one could try a higher test cap and try again from step 1.

5.
If the GCD function consistently returned $n$ itself, this could indicate that $a$ is in fact not coprime to $n$, in which case one could try going back to step 2 to pick a different $a$.

6.
Throw a failure exception.
For example, $n=221$. Of course it’s overkill to use the Pollard $p1$ algorithm on such a small number, but it helps to keep the example simple. Since the running time of the algorithm is exponential, Crandall and Pomerance suggest picking small $B$. So for this example let’s pick $B=10$, the primes are then 2, 3, 5, 7, and the exponents are 3, 2, 1, 1. Since 221 is odd, we try $a=2$. So we see that ${2}^{8}mod221=35$, and $\mathrm{gcd}(34,221)=17$. We also see ${3}^{9}mod221=14$ and $\mathrm{gcd}(13,221)=13$. Multiplication^{} immediately verifies that $13\times 17=221$.
As of version 5.2, Pollard’s $p1$ algorithm is one of the methods used by Mathematica’s FactorInteger
function after ferreting out small factors by trial division.
References
 1 R. Crandall & C. Pomerance, Prime Numbers^{}: A Computational Perspective, Springer, NY, 2001: 5.4.1
Title  Pollard’s $p1$ algorithm 

Canonical name  PollardsP1Algorithm 
Date of creation  20130322 16:43:47 
Last modified on  20130322 16:43:47 
Owner  PrimeFan (13766) 
Last modified by  PrimeFan (13766) 
Numerical id  8 
Author  PrimeFan (13766) 
Entry type  Algorithm 
Classification  msc 11A41 
Synonym  Pollard $p1$ algorithm 
Synonym  Pollard’s p minus 1 algorithm 
Synonym  Pollard p minus 1 algorithm 
Synonym  Pollard $p1$ method 
Synonym  Pollard’s p minus 1 method 
Synonym  Pollard p minus 1 method 
Synonym  Pollard’s $p1$ method 