** Next:** 11.2 Shanks' Baby step-Giant
** Up:** 11 Algorithms for groups
** Previous:** 11 Algorithms for groups

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*_{0},
*S*_{1}, ..., *S*_{r} (which are specified by their membership functions
). We now define a collection of maps as follows. Start with a
``random'' element *x*_{0} of the group. Let
*v*_{0} = (0,..., 0) be the
origin in the group
^{r}. We define an iterated map as follows
(

*x*_{i + 1},

*v*_{i + 1}) =

(

*x*_{i},

*v*_{i}) =

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*_{1}, *a*_{2},..., *a*_{r}), then
*g*_{i}^{ai} = 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
*a*_{i} is the shortest. That is also an estimate of
the number of steps upto a small constant factor.

** Next:** 11.2 Shanks' Baby step-Giant
** Up:** 11 Algorithms for groups
** Previous:** 11 Algorithms for groups
Kapil Hari Paranjape
2002-10-20