50 Years of the rho method

The "Birthday Problem" is the surprising statement that in a group of 23 people, chosen at random, there is a probability close to 50% that two share a birthday.  The following more general statement has important applications to computer science.  Pick integers at random in the interval (I, 2, ... , n) until some integer is repeated.  The expected number of choices required is close to sqrt(pi*n/2) = 1.253*sqrt(n). 

The "rho method", also known as "Pollard rho",  is an application of the birthday problem to factoring,  It was discovered on 8th June, 1974  and is described in my paper 6 (see list of papers on the Number Theory page).   Two days earlier I had a weaker algorithm (see list of problems below).  The same names are often used for the first of my two methods for discrete logarithms (my paper 9) , which also uses the birthday problem.  The other method of this paper is the "kangaroo method".  This page will be about these algorithms, and other related things.  For a detailed discussion see, Steven Galbraith, "Mathematics of Public Key Cryptography", CUP, 2012 ( the text is accessible on his website).

In my paper 4,  published in 1974,  I proved that deterministic factoring is possible in time O(n**1/4 + e).  My method used the FFT.   The same result was obtained by Strassen in a different way.  This result has only been improved recently by David Harvey (Math.  Comp. 2021), who obtained exponent 1/5.  The rho method of factoring was found while looking for an easier practical way to find small factors.

For about 10 years the rho method (together with the p-1 method) was the best way to find small factors.  A version was used by Richard Brent in 1980 (my paper 12) to find the 16 digit factor of F8 (the Eighth Fermat Number) - the cofactor of 62 digits was shown to be prime.  It became obsolete for large calculations with the arrival of Lenstra's Elliptic Curve Method(ECM), published in 1987.  As far as I know, the largest factor ever found by the rho method was 19 digits.  With today's computers, this record could be improved a little.  But there is no point, since the  current record for ECM is 83 digits. (In the case of a number composed of two factors of fairly equal sizes, the fastest factoring method is the Number Field Sieve, which can currently factor general numbers of more than 200 digits - see papers 14-17).

The rho method for discrete logs was originally proposed for the integers modulo a prime p, but applies to an arbitrary group . It is still the best method for d logs on an arbitrary elliptic curve over a finite field.     My second method, which I prefer to call the kangaroo method rather than the lambda method, computes a d log known to lie in an interval.   As explained in my paper 9,  the idea is to use a tame kangaroo to catch a wild kangaroo.  In the paper of Galbraith, Pollard and Ruprai (my paper 21) it is shown that 3 kangaroos are better than 2, and 4 better still.   Both the rho and kangaroo methods have useful parallel versions. 

A third method of computing d logs by random walks was first proposed by P, Gaudry and E. Schost (ANTS VI, 2004).  This uses a large number of short random walks and works in a multidimensional interval.

Both rho methods are widely taught, as one can see by putting "Pollard rho" into Google or YouTube.   I would guess this is because they are so simple.  They also illustrate very well some important points about algorithms:

i.    There may be faster methods than the obvious ones.

ii.   A proof that an algorithm works is not essential!   We do not have it for either rho method. 

The moral is that inventing algorithms is different to proving theorems.


......................................................................................................................................................................................................


Some problems (which mainly involve the number 2/3!):

(last edited 28/6/24).