11.5 Applicability and efficiency

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<sub>i</sub> 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.