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

5. Set x to Since d = x 2 - a , then x =
6. Set y to be , since d = x 2 - a is a perfect square, and is now our y 2 .
7. Return two factors, x + y and x - y .
For a simple example, Figure 3-3 shows this algorithm being run on the number 88.
Figure 3-3 Fermat's difference of squares method for finding factors of 88.
3.3.2.1 Analysis of Fermat's Difference of Squares
The running time of Fermat's difference of squares method is on the order of running time with constant
space requirements. Although this algorithm provides essentially no improvement to trial division, the concept
it uses is a fundamental building block upon which other factoring methods are built.
3.3.3 Pollard's ρ
Pollard has come up with several very clever mechanisms for factoring integers, as well as other ones we shall
study below in this chapter.
Pollard's rho ( ρ ) method works by finding cycles in number patterns. For example, using the modular arith-
metic from the previous chapter, we may want to successively square the number, say, 2, repeatedly modulo 14.
This would result in a sequence
2, 4, 8, 2, 4, 8,...
This sequence repeats itself forever. Pollard figured out a way to have these sequences give us clues about
the factors of numbers.
We'll show the algorithm, and then explain the nifty trick behind it.
Pollard's ρ. Factors an integer, a.
1. Set b to be a random integer between 1 and a - 3, inclusive.
2. Set s to be a random integer between 0 and a - 1, inclusive.
3. Set A = s.
4. Set B = s.