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

5. Define the function f ( x ) = ( x 2 + b) mod a .
6. Let g = 1.
7. If g ≠ 1, then go to Step 8.
(a) Set A = f (A).
(b) Set B = f ( f ( B )).
(c) Set g = gcd( A - B, a ).
(d) Repeat (go to Step 7).
8. If g is less than a , then return g . Otherwise, the algorithm failed to find a factor.
Why does this work? Well, the first leap of faith is that the function f ( x ) will randomly jaunt through the
values in the field. Although it is fairly simple (just a square with a constant addition), it will work, in general.
The second notion here is what is going on with the function calls. The value B is “moving” through the
values of the field (values modulo a) twice as “fast” (by calling the function f twice). This will give two pseu-
dorandom sequences through the elements of the field.
Listing 3-3 shows a simple implementation of this program in Python, and Figure 3-4 shows an example run
of the program.
Listing 3-3 Python code for Pollards ρ algorithm for factoring integers.
# Euclidean algorithm for GCD
def gcd(x, y):
if y == 0:
return x
else:
return gcd(y, x % y)
# Stepping function
def f(x, n):
return (x * x + 3) % n
# Implements Pollard rho with simple starting conditions
def pollardrho(a):
x = 2
y = 2
d = 1
while d == 1:
x = f(x, a)
y = f(f(y, a), a)
d = gcd(abs(x - y), a)
if d > 1 and a > d:
return d
if d == a:
return -1