Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

Applying sieving to the computation
of quadratic class groups


Author: Michael J. Jacobson Jr.
Journal: Math. Comp. 68 (1999), 859-867
MSC (1991): Primary 11Y40; Secondary 11Y16
MathSciNet review: 1604324
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present a new algorithm for computing the ideal class group of an imaginary quadratic order which is based on the multiple polynomial version of the quadratic sieve factoring algorithm. Although no formal analysis is given, we conjecture that our algorithm has sub-exponential complexity, and computational experience shows that it is significantly faster in practice than existing algorithms.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y40, 11Y16

Retrieve articles in all journals with MSC (1991): 11Y40, 11Y16


Additional Information

Michael J. Jacobson Jr.
Affiliation: Technische Universität Darmstadt, FB Informatik, Institut für theoretische Informatik, Alexanderstr. 10, 64283 Darmstadt, Germany
Email: jacobs@cdc.informatik.tu-darmstadt.de

DOI: http://dx.doi.org/10.1090/S0025-5718-99-01003-0
PII: S 0025-5718(99)01003-0
Keywords: Quadratic order, class group, sieving
Received by editor(s): May 5, 1997
Received by editor(s) in revised form: August 4, 1997
Additional Notes: The author is supported by the Natural Sciences and Engineering Research Council of Canada
Article copyright: © Copyright 1999 American Mathematical Society