Order computations in generic groups
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/38881 |
| _version_ | 1811081011001294848 |
|---|---|
| author | Sutherland, Andrew V |
| author2 | Michael F. Sipser. |
| author_facet | Michael F. Sipser. Sutherland, Andrew V |
| author_sort | Sutherland, Andrew V |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007. |
| first_indexed | 2024-09-23T11:40:22Z |
| format | Thesis |
| id | mit-1721.1/38881 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:40:22Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/388812019-04-12T15:42:55Z Order computations in generic groups Sutherland, Andrew V Michael F. Sipser. Massachusetts Institute of Technology. Dept. of Mathematics. Massachusetts Institute of Technology. Dept. of Mathematics. Mathematics. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2007. This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. Includes bibliographical references (p. 205-211). 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 [theta](N^1/2) group operations to compute abs([alpha])=N. A lower bound of [omega](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/loglogN)^1/2) when N is prime, but for nearly half the integers N..., 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 [alpha] for all [alpha]... in near linear time plus the cost of single order computation with N=[lambda](S), where [lambda](S)=lcm[alpha] over [alpha]... For abelian groups, a random S...G or constant size suffices to compute [lamda](G), the exponent of the group. Having computed [lambda](G), we show that in most cases the structure of an abelian group G can be determined using an additional O(N^[delta]/4) group operations, given and O(N^[delta]) bound on abs(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 [omega](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 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 by Andrew V. Sutherland. Ph.D. 2007-09-27T19:30:26Z 2007-09-27T19:30:26Z 2007 2007 Thesis http://hdl.handle.net/1721.1/38881 166229073 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 211 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Mathematics. Sutherland, Andrew V Order computations in generic groups |
| title | Order computations in generic groups |
| title_full | Order computations in generic groups |
| title_fullStr | Order computations in generic groups |
| title_full_unstemmed | Order computations in generic groups |
| title_short | Order computations in generic groups |
| title_sort | order computations in generic groups |
| topic | Mathematics. |
| url | http://hdl.handle.net/1721.1/38881 |
| work_keys_str_mv | AT sutherlandandrewv ordercomputationsingenericgroups |