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 ?(*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 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*(*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(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(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.