0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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%.

(As regards your prior question, they have an analysis in section 8 of empirical data for the sufficiently random-ness of iterated polynomials for this method.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – T. Ingram Dec 17 '17 at 18:56
  • $\begingroup$ @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. $\endgroup$ – Eric Towers Dec 18 '17 at 3:38
  • $\begingroup$ 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. $\endgroup$ – T. Ingram Dec 18 '17 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.