Programming Praxis

We examined John Pollard’s rho algorithm for factoring integers in a previous exercise. In today’s exercise we will consider some improvements to the basic algorithm.

Let’s begin with a quick refresher. Consider the sequence xx_n+1 = (x_n)² + c (mod n), which becomes cyclic in approximately √n steps. If n = p q with p and q relatively prime, then there will be a pair of numbers x_i and x_j such that p = gcd(|x_i – x_j|, n). The rho algorithm runs the sequence, for random x₀ and c, looking for the pair of numbers x_i and x_j for which the gcd is between 1 and n, giving a factor of n.

If the sequence becomes cyclic without finding a factor, it is necessary to try again with different values of x₀ and c. Pollard used Robert Floyd’s tortoise-and-hare cycle finding algorithm, which compares the values of x_i (the “tortoise”) and x_2i (the “hare”, because it moves twice as fast through the cycle as the tortoise); if they are ever equal, a cycle has been identified. Later, Richard Brent devised an alternate method of cycle detection. Each time i is a power of two, the value of x_i is saved; if a subsequent x_j = x_i is found before j = 2i, a cycle has been identified. Brent’s cycle-finding algorithm requires only one modular multiplication per step, instead of the three modular multiplications required by Floyd’s cycle-finding algorithm, so even though Brent’s method typically requires more steps that Floyd’s method, in practice the number of modular multiplications is generally about a quarter less than Floyd’s method, giving a welcome speed-up to Pollard’s factoring algorithm.

There are two other improvements to Pollard’s algorithm that apply to both the Floyd and Brent variants. First, it may be useful to perform trial division to find small divisors before the main algorithm starts; it is certainly necessary to remove factors of 2, and removing larger factors can also save time. Second, because the gcd required at each step is computationally expensive, the numbers |x_i – x_j| may be accumulated (multiplied all together) modulo n for several steps, then the gcd of the modular product is taken with n. If the number of steps between gcd operations is, say, 100, the cost of a gcd at each step is replaced by the cost of a modular multiplication, which is smaller.

Your task is to write two versions of the Pollard rho function, one using Floyd’s cycle-finding algorithm, the other using Brent’s cycle-finding algorithm, both versions using trial division to identify small factors and both using the short-circuit gcd procedure, and to compare timings to determine which algorithm, using which parameters for the limit of trial division and the limit of the gcd short-circuit, makes the fastest implementation of Pollard’s algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2