# Pollard's rho without directly checking for collisions

This is after this other question answered. In the previous question, I understood that to look for a collision without Floyd's algorithm would be space costly. Now I have this new question.

Suppose we have a collision mod $p$ given two random numbers. Then AFAIK we're guaranteed to have found a factor of $N$, whether it's $N$ itself or some non-trivial factor. This will be discovered by the gcd computation. So why should I look for collisions directly in the sequence mod $N$? Won't the gcd tell me so?

To look at the question a little closer, I wrote the following program. It uses the random number generator from Python and checks whether the algorithm has had a certain amount of chance. If it goes beyond that limit, we stop with failure. (I chose the limit $2 \sqrt{N}$.)

def rho_random(N):
chances = 0
def random_mod_N():
i = random.randint(1, N - 1)
return i
while True:
if 2*int(sqrt(N)) <= chances:
return "unlucky"
a = random_mod_N()
b = random_mod_N()
d = gcd(a - b, N)
chances = chances + 1
if d == N:
return "trivial factor"
if 1 < d and d < N:
return d


Thank you.

Greatest common divisor computations are expensive in time, compared to not doing them. The variant of Pollard and Brent takes, for example, $100$ candidates, multiplies them together, then computes the $\gcd$. This replaces $100$ $\gcd$s with $99$ multiplies and $1$ $\gcd$. Multiplies (modulo $N$) are vastly faster than $\gcd$s ($O(\log n)$ faster from here).
Pollard and Brent describe and analyze this variant in Brent, Richard P. (1980), "An Improved Monte Carlo Factorization Algorithm", BIT 20: 176–184, doi:10.1007/BF01933190. This idea is described in section 5 of the cited paper. In section 7, they discuss not even multiplying in $|x_i-x_j|$ with $i$ and $j$ too close. With this modification, their runtimes reduce by about 24%.
• I'm a little lost. Is the polynomial really required or is it the case that any random source will do? After reading section 5 of the cited paper, I had the impression that rho_random would be the variation discussed in section 5. Brent says we can replace the done := (x = y) with done := gcd(...) which I think is what rho_random does. But Brent still uses a polynomial and rho_random doesn't. – T. Ingram Dec 17 '17 at 18:56
• @T.Ingram : They first talk about using iteration of a polynomial to produce a sequence of values. Then at "It is plausible to assume that $f \,(\mod{p})$ behaves like a 'random' function and ...", they switch to assuming that your sequence of $x_n$ is "random". Then they talk about avoiding too many $\gcd$ calculations by batching them up. Your rho_random does use the $\gcd$ termination condition, but does more $\gcd$s than is likely optimal. – Eric Towers Dec 18 '17 at 3:38
• Okay. That's understood. It does more gcds than another procedure which batches them up. But check this out. I have two procedures whose only difference AFAIK is the source of randomness. They both compute a factor, but the one with the polynomial is much faster than the one with Python's random as source of randomness. See this. – T. Ingram Dec 18 '17 at 12:20