We consider the problem of computing the order of an element ? in a generic group G. The two standard algorithms, Pollard's rho method and Shanks' baby-steps giant-steps technique, both use ?(N1/2) group operations to compute |?| = N. A lower bound of ?(N1/2) has been conjectured. We disprove this conjecture, presenting a generic algorithm with complexity o(N1/2). The running time is O((N loglog N)1/2) when N is prime, but for nearly half the integers N ? [0,M], the complexity is O(N1/3). If only a single success in a random sequence of problems is required, the running time is subexponential in log N.
We prove that a generic algorithm can compute |?| for all ??S?G in near linear time plus the cost of a single order computation with N = ?(S),
where ?(S) = lcm |?| over ??S. For abelian groups, a random S?G of constant size suffices to compute ?(G), the exponent of the group. Having computed ?(G), we show that in most cases the structure of an abelian group G can be determined using an additional O(N?/4) group operations, given an O(N?) bound on |G| = N. The median complexity is approximately O(N1/3) for many distributions of finite abelian groups,
and o(N1/2) in all but an extreme set of cases. A lower bound of ?(N1/2) had been assumed, based on a similar bound for the discrete logarithm problem.
We apply these results to compute the ideal class groups of imaginary quadratic number fields, a standard test case for generic algorithms. The record class group computation by a generic algorithm,
for discriminant -4(1030+1), involved some 240 million group operations over the course of 15 days on a Sun SparcStation4. We accomplish the same task using 1/1000th the group operations,
taking less than 3 seconds on a PC. Comparisons with non-generic algorithms for class group computation are also favorable in many cases.
We provide tables of class groups with discriminants of the form -4(2n+1), -(2n-1), -4(10n+1), and -(10n+3),
and also present results for several 101-digit negative discriminants. These are believed to be the largest class groups ever computed.