A space efficient algorithm for group structure computation

Open Access
Publisher Website
Google Scholar
Abstract
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 (with denoting the group order), and we explicitly determine the -constants. We implemented our algorithm for ideal class groups of imaginary quadratic orders and present experimental results.

This publication has 9 references indexed in Scilit: