International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at) iacr.org.

Details

Andrew V. Sutherland (#491)
Name Andrew V. Sutherland
Personal Homepage http://math.mit.edu/~drew
Topic of his/her doctorate. Order Computations in Generic Groups
Category foundations
Keywords number theory
Ph.D. Supervisor(s) Michael Sipser, Ronald Linn Rivest
Year of completion 2007
Abstract

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.

E-Mail Address drew (at) math.mit.edu
Last Change 2011-04-27 09:26:39
To provide an update on this entry, please click .

Contact: phds (at) iacr.org

[ IACR home page ] [ IACR PhDs page ] © IACR