Computer Security and Cryptography

13.4 POLLARD'S ρ-ALGORITHM [POLLARD, 1978]

If positive integers x and y in can be found so that 1 < d = gcd{x − y, N} < N, then d is a factor of N.

Pairs (x, y) can be found by random trials, hence the name Monte Carlo; accordingly, a random function f mapping the integers in into themselves is selected. The sequence x₁, x₂, … is determined by the rule

As we observed in Chapter 9, the f(n) must repeat before N − 1 iterations and the sequence

has

• A tail x₁ → x₂ = f(x₁) → · · · → x_k = f(x_k−1), and
• Then enters a loop or cycle x_k = f(x_k−1) → … → x_j+k = f(x_j+k−1) = x_k.

The name ρ chosen by Pollard for his algorithm is perfectly clear; the iterates of the mapping f appear like the Greek letter ρ.

Unfortunately N = O (2¹⁰⁰) so that j + k could be very large and we cannot wait · · · and we do not have to, because of the Birthday Paradox.

13.4.1 The Birthday Paradox

What is the probability Pr{E_n} that in a class of n students, that no day is the birthday of two or more students?

Answer: Assuming that a year contains 365 days, the probability that no two students in a class of n have the ...