2.4.2 Pollard's (p-1)-Factoring Algorithm

Pollard's (p-1)-Factoring Algorithm is a special purpose algorithm for finding efficiently primes p for which p-1 is smooth with respect to some relatively small bound B. Therefor following

Definition:
Let be 0 > B ∈ Z. An n ∈ Z is said to be B-smooth or smooth with respect to B if all its prime factors are ≤ B.

The idea behind (p-1)-algorithm is the following:
Let B be a smoothness bound. Let Q be the least common multiple of all powers of primes ≤ B, that are ≤ n. If g^l ≤ n, then l⋅ ln q ≤ ln n and l ≤ ⌊ ln n / ln q ⌋. Thus Q = ∏_{q ≤ b} q^{⌊ ln n / ln q ⌋} where the product is over all distinct q ≤ B. If p is prime factor of n, so that p-1 is B-smooth, then p-1|Q and consequently for any a, for which is gcd(a, p) = 1, Fermat's theorem implies that a^Q ≡ 1 (mod p). Hence if d = gcd(a^Q - 1, n ), then p|d.

It is possible, that d = n. In this case the algorithm fails. However this is unlikely to occur if n has at least two large distinct prime factors.

Example

Let n = 27869. Now choose a smoothness bound B, e.g. B = 8 and choose a further number a₀, where 2 ≤ a₀ ≤ n-1, in this case e.g. a = 3.
In the first step we compute gcd(a₀ , n) = gcd(3, 27869) = 1. (If we got d ≠ 1 so we would have our non-trivial factor already) .
Now you compute for every single prime factor q_i ≤ B:
1. l_i = ⌊ ln n / ln q_i ⌋
2. a_i+1 = a_i^ql_i mod n
Hence:
a₀ = 3,
q₁ = 2, l₁ = ⌊ ln n / ln q₁ ⌋ = ⌊ 10,23527 / 0.69315 ⌋ = 14, a₁ = 14465
q₂ = 3, l₂ = 9, a₂ = 17337
q₃ = 5, l₃ = 6, a₃ = 18787
q₄ = 7, l₄ = 5, a₄ = 3597
gcd(a₄ - 1, n) = gcd(3596, 27869) = 899.

In the Applet the algorithm was implemented in a way that after every computation of a, the greatest common divisor is computed. There are numerous other practical improvements of this method.

Applet (p-1)-Algorithm:

Quellcode:
PmeAlgSF.java - Applet surface
PmeAlg.java - Algorithm class

2.4.3 RSA-Faktoring