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*&sube*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*(*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^{30}+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^{n}+1), -(2^{n}-1), -4(10^{n}+1), and -(10^{n}+3),
and also present results for several 101-digit negative discriminants. These are believed to be the largest class groups ever computed.