** Next:** A. A missing Lemma
** Up:** 11 Algorithms for groups
** Previous:** 11.5 Applicability and efficiency

Another useful tool goes by the name ``Index Calculus''. Suppose that
we are given a set of generators *g*_{1}, ..., *g*_{r} of *G* and * another* ``black-box'' which computes a function
*A* : *G*×*R*^{r}; here *R* is used to denote random input. The property of
*A* is that given (*g*, *k*) (with *k* random) the output is an *r*-tuple
(*a*_{1},..., *a*_{r}), such that with probability greater than
1 - (1/2)^{r + t} (for some small integer *t*) we have the relation
*g*^{k} =

*g*_{i}^{ai}
(Note that one can quickly check whether this is indeed true). We can
use such a black-box *A* to give a probabilistic solution to the group
structure problem. By running the algorithm at most *r* + *t* times we
will (with high probability) obtain sufficiently many relations to
write *g* in terms of the elements *g*_{i}. Thus we can use this to
construct a probabilistic algorithm that splits the map
^{r}*G*
as required.
Since this algorithm makes use of one additional ``black-box'' it is
not a ``generic group algorithm''.

** Next:** A. A missing Lemma
** Up:** 11 Algorithms for groups
** Previous:** 11.5 Applicability and efficiency
Kapil Hari Paranjape
2002-10-20