Factoring and Discrete Logarithms - Modern Cryptanalysis: Techniques for Advanced Code Breaking - page 58

Figure 3-4 Pollard's ρ factorization of 2,262,599, with b = 2, s = 2.
The reason this algorithm is called the ρ algorithm is because, if drawn out on paper, the paths of the two
values, A and B, chase each other around in a way that resembles the Greek letter ρ (see Figure 3-5 ) .
Figure 3-5 Figure showing the path of a run of the Pollard ρ algorithm. The path will eventually loop back
upon itself, hence the name “ρ.” The algorithm will detect this loop and use it to finda factor.
3.3.3.1 Analysis of Pollard's ρ
The Pollard ρ algorithm has time complexity of approximately O ( n 1/4 ) for finding a factor and no significant
amount of storage [15]. Completely factoring a number will take slightly more time, but finding the first factor
will usually take the longest.
3.3.4 Pollard's p - 1
John M. Pollard also has another method attributed to him for factoring primes [12]. Pollard's p - 1 method
requires that we have a list of primes up to some bound B. We can label the primes to be, say, p 1 = 2, followed
by p 2 = 3, and p 3 = 5, and so on, all the way up to the bound B. There are already plenty of lists of primes to be
found on the Internet, or they could be generated with a simple brute-force algorithm as described above, since
we don't need very many of them (only a few thousand in many cases).
The algorithm works by Fermat's little theorem, that is, given a prime p and any integer b, then
b p- 1 ≡ 1 (mod p )
We want to find p such that p is a prime factor of a, the number we are trying to factor. If L is some multiple of
(p - 1), then p | gcd(b L - 1, a). The best way to try to get L to be a multiple of (p - 1) is to have L be a multiple
of several prime factors. We can't compute b L mod p, but we can compute b L mod a. The algorithm works by