January 21, 2011
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 xxn+1 = (xn)2 + 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 xi and xj such that p = gcd(|xi – xj|, n). The rho algorithm runs the sequence, for random x0 and c, looking for the pair of numbers xi and xj 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 x0 and c. Pollard used Robert Floyd’s tortoise-and-hare cycle finding algorithm, which compares the values of xi (the “tortoise”) and x2i (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 xi is saved; if a subsequent xj = xi 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 |xi – xj| 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.