11.1 Pollard's $\rho$

This method uses the least amount of information about the group and also uses the least amount of storage. We choose a ``random'' partition of the elements of the group into disjoint sets S<sub>0</sub>, S<sub>1</sub>, ..., S<sub>r</sub> (which are specified by their membership functions $\mu_{i}^{}$). We now define a collection of maps as follows. Start with a ``random'' element x₀ of the group. Let v₀ = (0,..., 0) be the origin in the group $\mathbb {Z}$^r. We define an iterated map as follows

(x_{i + 1}, v_{i + 1}) = $$\Phi$$(x_i, v_i) = $$\begin{cases} (x_i^2,2\cdot v_i) & x_i\in S_0 \\ (g_j\cdot x_i,e_j + v_i) & x_i\in S_j \\ \end{cases}$$

By the techniques due to Pollard, Brent and Floyd described earlier we can find an integer T such that (x_2T, v_2T) = (x_T, v_T). It follows that if v_2T - v_T = (a₁, a₂,..., a_r), then

$$\prod_{i}^{}$$g_i^a_i = 1

Some aspects of Brent's method can be used to further ensure that v_i does not grow too large (since we are only interested in v_2T - v_T). Assuming that the choice of S_i is ``random'' enough we should be close to a relation of the smallest size in the sense that $\sum_{i}^{}$a_i is the shortest. That is also an estimate of the number of steps upto a small constant factor.