Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Two efficient algorithms for the computation of ideal sums in quadratic orders

Author: André Weilert
Journal: Math. Comp. 75 (2006), 941-981
MSC (2000): Primary 54C40, 14E20; Secondary 46E25, 20C20
Published electronically: December 8, 2005
MathSciNet review: 2197002
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper deals with two different asymptotically fast algorithms for the computation of ideal sums in quadratic orders. If the class number of the quadratic number field is equal to 1, these algorithms can be used to calculate the GCD in the quadratic order. We show that the calculation of an ideal sum in a fixed quadratic order can be done as fast as in $ \mathbf{Z}$ up to a constant factor, i.e., in $ O(\mu(n) \log n),$ where $ n$ bounds the size of the operands and $ \mu(n)$ denotes an upper bound for the multiplication time of $ n$-bit integers. Using Schönhage-Strassen's asymptotically fast multiplication for $ n$-bit integers, we achieve $ \mu(n)=O(n\log n\log\log n).$

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 54C40, 14E20, 46E25, 20C20

Retrieve articles in all journals with MSC (2000): 54C40, 14E20, 46E25, 20C20

Additional Information

André Weilert
Affiliation: Department of Computer Science II, University of Bonn, Römerstraße 164, 53117 Bonn, Germany
Address at time of publication: Liliencronstr. 8, 12167 Berlin, Germany

Keywords: Computational number theory, quadratic number fields, GCD computation, Euclidean algorithm
Received by editor(s): July 20, 2003
Received by editor(s) in revised form: January 7, 2005
Published electronically: December 8, 2005
Additional Notes: This paper deals with the main results of my doctoral thesis [40]. I would like to thank my academic teachers Arnold Schönhage and Jens Franke (both at the University of Bonn, Germany).
Article copyright: © Copyright 2005 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.