1
$\begingroup$

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?
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I'll test your result with the code if I've time, or you can do it to improve your answer. $\endgroup$ – kelalaka Mar 27 at 19:48
  • $\begingroup$ 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. $\endgroup$ – Aman Grewal Mar 27 at 21:14

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.