** Next:** 11.6 Index calculus
** Up:** 11 Algorithms for groups
** Previous:** 11.4 Other problems

The fundamental theorem for finite abelian groups states that every
abelian group is isomorphic to product of cyclic groups. We have seen
that the all-pervading question in algorithmic abelian group theory is
``To what extent can we (efficiently) compute this isomorphism and its
inverse?'' Because of the efficiency aspect it is important to count
the number of steps and the amount of storage that our algorithms
require. In such measurement numbers of the size of the cardinality of
*F* are considered ``large'', numbers of the size of the number of
bits in the *elements* of *F* are considered ``reasonable'' and
numbers of the size of the logarithm of the latter number are
considered ``small'' or insignificant.
One can show that the expected running time of the algorithms
described above is of the same order as the bounds available. Since
these bounds are crudely measured as the order of the group *G* this
makes the algorithms ``slow''. However, in a given case where not
enough information is available or it is suspected that the elements
*g*_{i} generate a much smaller group one can start with artificially
chosen small bounds and run the algorithms; if the assumptions (on the
``real'' bounds) are valid these will run to completion.

** Next:** 11.6 Index calculus
** Up:** 11 Algorithms for groups
** Previous:** 11.4 Other problems
Kapil Hari Paranjape
2002-10-20