A space efficient algorithm for group structure computation
Edlyn Teske · Mathematics of Computation · 1998
We present a new algorithm for computing the structure of a finite abelian group, which has to store only a fixed, small number of group elements, independent of the group order. We estimate the computational complexity by counting the group operations such as multiplications and equality checks. Under some plausible assumptions, we prove that the expected run time is O ( n ) O(\sqrt {n}) (with n n denoting the group order), and we explicitly determine the O O -constants. We implemented our algorithm for ideal class groups of imaginary quadratic orders and present experimental results.