1

In the original paper of Pollard's Monte Carlo Methods for Index Computation (mod p):

When the epact is reached, i.e. $$x_i = x_{2i}.$$ then the following equation is formed $$q^m \equiv r^n \pmod p,$$ where where $m=a_e- a_{2e} \pmod{p - 1}$ and $n = b_{2e} - b_e \pmod{p - 1}$.

with ext-GCD, the Bézout's identity calculated $d = \lambda m + \mu (p - 1).$ Raising the above eqution to the $\lambda$ power gives $$q^d \equiv r^{\lambda n} \pmod{p}$$

After this, it is claimed that $\lambda n$ is of the form $dk$ and then

$$q \equiv r^k \theta^i \pmod p,$$ where $\theta \equiv r^{(p-1)/2}$ is a $d$ root of unity, and $i (0 \leq u \leq d-1)$ remains to be determined.

Questions:

  1. Why $\lambda n$ is of the form $dk$
  2. In Wikipedia's sample code for Pollard's Rho algorithm, there is no such determination of $i$ (note that the $i$ in the article is not the counter of the code). Why is this so?
kelalaka
  • 45,607
  • 9
  • 104
  • 179

1 Answers1

1

1) Because $r$ is a primitive root, there exists a $k$ such that $r^k = q$, so $r^{dk} = q^d$.

2) The sample code (lifted from section 3.6.3 of the Handbook of Applied Cryptography http://cacr.uwaterloo.ca/hac/about/chap3.pdf) assumes that the group has prime order. Pollard doesn't make this assumption.

Aman Grewal
  • 1,381
  • 1
  • 7
  • 22
  • I'll test your result with the code if I've time, or you can do it to improve your answer. – kelalaka Mar 27 '20 at 19:48
  • I don't know what you mean by test it with the code. The c++ on the wikipedia article doesn't implement the full algorithm, so I can't just tweak it. – Aman Grewal Mar 27 '20 at 21:14