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!):
My first version of the rho method (of factoring) had exponent 2/3, and does not resemble a Greek letter. Can you guess what it was? (It is a foolish algorithm when you know the rho method).
If the kangaroo has only two jumps, the best exponent is 2/3 (see paper 9). What is it with three jumps? (Perhaps this has been solved long ago?).
Give a deterministic algorithm to compute discrete logs (mod p) which is faster OR uses less storage (or both) than the well-known "Baby Step - Giant Step" method. Of course, it is easy to reduce the storage whilst increasing the time.
Consider this problem: find the solutions, if any, of the equation: x = dlog x, (1<=x<=p-2) when the base of logs is given. There are interesting algorithms, some with time O(p**2/3), (see my page "The equation x = dlog x"). Improve these algorithms, or invent better ones. A harder problem still is to give a deterministic algorithm for this problem, faster than O(p).
See my page "The Endgames KRK and KQK" for a "number-theoretic" chess problem involving only three pieces (of which 2/3 are White!).
(last edited 16/10/24).