We consider the problem of computing the order of an element in a generic group. The two standard algorithms, Pollard's rho method and Shanks' baby-steps giant-steps technique, both use Θ(N^1/2) group operations to compute |α| = N. A lower bound of Ω(N^1/2) has been conjectured. We disprove this conjecture, presenting a generic algorithm with complexity o(N^1/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(N^1/3). If only a single success in a random sequence of problems is required, the running time is subexponential.

We prove that a generic algorithm can compute |α| for all α∈S&subeG 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(N^1/3) for many distributions of finite abelian groups, and o(N^1/2) in all but an extreme set of cases. A lower bound of Ω(N^1/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(10³⁰+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(2ⁿ+1), -(2ⁿ-1), -4(10ⁿ+1), and -(10ⁿ+3), and also present results for several 101-digit negative discriminants. These are believed to be the largest class groups ever computed.