Order computations in generic groups

Abstract

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/log log 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 Jal 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(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 successfully computed several class groups with discriminants containing more than 100 digits. These are believed to be the largest class groups ever computed. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax [phone].)