Pollard's p1 algorithm
From Academic Kids

Pollard's p − 1 algorithm is a number theoretic integer factorization algorithm, invented by John Pollard in 1974. It is a specialpurpose algorithm, meaning that it is only suitable for integers with specific types of factors.
The algorithm is based on the insight that numbers of the form a^{b} − 1 tend to be highly composite when b is itself composite. Since it is computationally simple to evaluate numbers of this form in modular arithmetic, the algorithm allows one to quickly check many potential factors with great efficiency. In particular, the method will find a factor p if b is divisible by p − 1, hence the name. When p − 1 is smooth (the product of only small integers) then this algorithm is wellsuited to discovering the factor p.
Contents 
Base concepts
Let n be a composite integer with prime factor p. By Fermat's little theorem, we know that
 <math>
a^{p1} \equiv 1\pmod{p}<math> for <math>a \in (\mathbb{Z}/p\mathbb{Z})^* <math>
Let us assume that p − 1 is Bpowersmooth for some reasonably sized B (more on the selection of this value later). Recall that a positive integer m is called Bsmooth if all prime factors p_{i} of m are such that p_{i} ≤ B. m is called Bpowersmooth if all prime powers p_{i}^{ei} dividing m are such that p_{i}^{ei} ≤ B.
Let p_{1}, ..., p_{L} be the primes less than B and let e_{1}, ..., e_{L} be the exponents such that
 <math>
p_i^{e_i} \le B < p_i^{e_i + 1} <math>
Let
 <math>
M = \prod_{i = 1}^{L} p_i^{e_i} <math>
As a shortcut, note that M = lcm{1, ..., B}. As a consequence of this, (p − 1) divides M, and also if p^{e} divides M this implies that p^{e} ≤ B. Since (p − 1) divides M we know that a^{M} ≡ 1 (mod p), and because p divides n this means gcd(a^{M} − 1, n) > 1.
Therefore if gcd(a^{M} − 1, n) ≠ n, then the gcd is a nontrivial factor of n.
Note that if p − 1 is not Bpowersmooth, then a^{M} ≢ 1 (mod p) for at least half of all a.
Pollard concepts
Let n = pqr, where p and q are distinct primes and r is an integer, such that p − 1 is Bpowersmooth and q − 1 is not Bpowersmooth. Now, gcd(a^{M} − 1, n) yields a proper factor of n.
Note that in the case where q − 1 is Bpowersmooth, the gcd may yield a trivial factor because q divides a^{M} − 1.
Note that this is what makes the algorithm specialized. For example, 172189 = 421 × 409. 421 − 1 = 2^{2}×3×5×7 and 409 − 1 = 2^{3}×3×17. So, an appropriate value of B would be from 7 to 16. If B was selected less than 7 the gcd would have been 1 and if B was selected higher than 16 the gcd would have been n. Of course, we do not know what value of B is appropriate in advance, so this will factor into the algorithm.
To speed up calculations, we also know that when taking the gcd we can reduce one part modulo the other, so gcd(a^{M} − 1, n) = gcd(a^{M} − 1 mod n, n). This can be efficiently calculated using modular exponentiation and the Euclidean algorithm.
Algorithm and running time
The basic algorithm can be written as follows:
 Inputs: n: a composite integer
 Output: a nontrivial factor of n or failure
 1. select a smoothness bound B
 2. pick a randomly in <math>(\mathbb{Z}/n\mathbb{Z})^*<math> (note: we can actually fix a, random selection here is not imperative)
 3. for each prime q ≤ B
 <math>e \gets \bigg\lfloor \frac{\log{B}}{\log{q}} \bigg\rfloor<math>
 <math>a \gets a^{q^e} \mod{n}<math> (note: this is a^{M})
 4. g ← gcd(a − 1, n)
 5. if 1 < g < n then return g
 6. if g = 1 then select a higher B and go to step 2 or return failure
 7. if g = n then go to step 2 or return failure
If g = 1 in step 6, this indicates that for all p − 1 that none were Bpowersmooth. If g = n in step 7, this usually indicates that all factors were Bpowersmooth, but in rare cases it could indicate that a had a small order modulo p.
The running time of this algorithm is O(B × log B × log^{2}n), so it is advantageous to pick a small value of B.
Large prime variant
A variant of the basic algorithm is sometimes used. Statistically, there is often a factor p of n such that p − 1 = fq such that f is Bpowersmooth and B < q ≤ B', where q is a prime and B' is called a semismoothness bound.
As a starting point, this would work into the basic algorithm at step 6 if we encountered gcd = 1 but didn't want to increase B. For all primes B < q_{1}, ..., q_{L} ≤ B', we check if
 <math>\gcd\left(a^{q_im}1, n\right) \neq 1<math>
to obtain a nontrivial factor of n. This is quickly accomplished, because if we let c = a^{M}, and d_{1} = q_{1} and d_{i} = q_{i} − q_{i − 1}, then we can compute
 <math>a^{q_1m} = c^{d_1}, a^{q_2m} = c^{d_1}c^{d_2} = a^{q_1m}c^{d_2}, \ldots<math>
The running time of the algorithm with this variant then becomes O(B' × log B' × log^{2}n).
Additional information
Because of this algorithm's effectiveness on certain types of numbers the RSA specifications require that the primes, p and q, be such that they are nonBpowersmooth for small values of B.de:Pollardp1Methode