# The dth root unity in the Pollard Rho Algorithm

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?

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