Mathematics of Computation

Author(s): André Weilert.
Journal: Math. Comp. 75 (2006), 941-981.
MSC (2000): Primary 54C40, 14E20; Secondary 46E25, 20C20
Posted: December 8, 2005
Retrieve article in: PDF

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

bounds the size of the operands and $\mu(n)$ denotes an upper bound for the multiplication time of

-bit integers. Using Schönhage-Strassen's asymptotically fast multiplication for

-bit integers, we achieve $\mu(n)=O(n\log n\log\log n).$

1.: T. M. Apostol, Modular Functions and Dirichlet Series in Number Theory, second ed., Grad. Texts in Math., vol. 41, Springer-Verlag, Berlin, 1997. MR 1027834 (90j:11001)
2.: R. Brauer, On the Zeta-Function of Algebraic Number Fields, Amer. J. Math. 69 (1947), 243-250. MR 0020597 (8:567h)
3.: -, On the Zeta-Function of Algebraic Number Fields II, Amer. J. Math. 72 (1950), 739-746. MR 0039009 (12:482g)
4.: J. Buchmann, C. Thiel, and H. Williams, Short Representation of Quadratic Integers, Computational Algebra and Number Theory (Sydney University, November 1992) (W. Bosma and A. van der Poorten, eds.), Math. Appl., vol. 325, Kluwer Academic Publishers, Dordrecht, Netherlands, 1995, pp. 159-185. MR 1344929 (96c:11144)
5.: D. A. Buell, Binary Quadratic Forms, Classical Theory and Modern Computations, Springer-Verlag, Berlin, 1989. MR 1012948 (92b:11021)
6.: B. F. Caviness, A Lehmer-Type Greatest Common Divisor Algorithm for Gaussian Integers, SIAM Rev. 15 (1973), no. 2, 414.
7.: B. F. Caviness and G. E. Collins, Algorithms for Gaussian Integer Arithmetic, Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation SYMSAC'76 (Yorktown Heights) (R. D. Jenks, ed.), 1976, pp. 36-45.
8.: H. Cohen, A Course in Computational Algebraic Number Theory, Grad. Texts in Math., vol. 138, Springer-Verlag, Berlin, 1996, Third, Corrected Printing.MR 1228206 (94i:11105)
9.: -, Hermite and Smith Normal Form Algorithms over Dedekind Domains, Math. Comp. 65 (1996), no. 216, 1681-1699.MR 1361805 (97e:11159)
10.: -, Advanced Topics in Computational Number Theory, Grad. Texts in Math., vol. 193, Springer-Verlag, Berlin, 2000. MR 1728313 (2000k:11144)
11.: G. E. Collins, A Fast Euclidean Algorithm for Gaussian Integers, J. Symbolic Comput. 33 (2002), 385-392. MR 1890576 (2003a:11159)
12.: C. F. Gauß, Untersuchungen über höhere Arithmetik (Disquisitiones Arithmeticae), Chelsea Publishing Company, Bronx, New York, 1889, Neudruck 1965, Übersetzung ins Deutsche von H. Maser (ed.). MR 0188045 (32:5488)
13.: J. L. Hafner and K. S. McCurley, Asymptotically Fast Triangulation of Matrices over Rings, SIAM J. Comput. 20 (1991), no. 6, 1068-1083. MR 1135749 (93d:15021)
14.: T. L. Heath, The Thirteen Books of Euclid's Elements, second ed., vol. 2, Cambridge University Press, New York, 1956, Books III-IX.MR 0075873 (17:814b)
15.: K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, second ed., Grad. Texts in Math., vol. 84, Springer-Verlag, Berlin, 1990. MR 1070716 (92e:11001)
16.: E. Kaltofen and H. Rolletschek, Arithmetic in Quadratic Fields with Unique Factorization, Proceedings of the EUROCAL'85 Conference on Computer Algebra (Linz, Austria, April 1-3, 1985) B. F. Caviness, ed., Lecture Notes in Comput. Sci., vol. 204, Springer-Verlag, Berlin, 1985, pp. 279-288. MR 0826569 (87c:11099)
17.: -, Computing Greatest Common Divisors and Factorizations in Quadratic Number Fields, Math. Comp. 53 (1989), no. 188, 697-720. MR 0982367 (90a:11154)
18.: D. E. Knuth, The Analysis of Algorithms, Actes du Congrès International des Mathématiciens (1/10 septembre 1970, Nice, France) (Paris) (Comité d'Organisation du Congrès, ed.), vol. 3, Gauthier-Villars, 1971, pp. 269-274.MR 0423865 (54:11839)
19.: -, Seminumerical Algorithms, third ed., The Art of Computer Programming, vol. 2, Addison-Wesley, Reading, MA, 1998.MR 0633878 (83i:68003)
20.: S. Lang, Algebra, third ed., Addison-Wesley, Reading, MA, 1993.MR 1878556 (2003e:00003)
21.: -, Algebraic Number Theory, second ed., Grad. Texts in Math., vol. 110, Springer-Verlag, Berlin, 1994. MR 1282723 (95f:11085)
22.: D. H. Lehmer, Euclid's Algorithm for Large Numbers, Amer. Math. Monthly 45 (1938), 227-233.
23.: F. Lemmermeyer, The Euclidean Algorithm in Algebraic Number Fields, Exposition. Math. 13 (1995), 385-416. MR 1362867 (96i:11115)
24.: H. W. Lenstra, Jr, On the Computation of Regulators and Class Numbers of Quadratic Fields, London Math. Soc. Lecture Note Ser. 56 (1982), 123-150. MR 0697260 (86g:11080)
25.: U. Manber, Introduction to Algorithms. A Creative Approach, Addison-Wesley, Reading, MA, 1989. MR 1091251 (93a:68002)
26.: J. Neukirch, Algebraic Number Theory, Grundlehren Math. Wiss., vol. 322, Springer-Verlag, Berlin, 1999. MR 1697859 (2000m:11104)
27.: D. J. Newman, Analytic Number Theory, Grad. Texts in Math., vol. 177, Springer-Verlag, Berlin, 1998. MR 1488421 (98m:11001)
28.: A. Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inform. 1 (1971), 139-144.
29.: -, IGCDOC, Computation of Integer GCD's, Unpublished Manuscript, 1987.
30.: -, Fast Reduction and Composition of Binary Quadratic Forms, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation ISSAC'91 (Bonn, Germany, July 15-17, 1991) S. M. Watt, ed., ACM Press, New York, 1991, pp. 128-133.
31.: A. Schönhage, A. F. W. Grotefeld, and E. Vetter, Fast Algorithms - A Multitape Turing Machine Implementation, BI Wissenschaftsverlag, Mannheim, Germany, 1994. MR 1290996 (96c:68043)
32.: A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen, Computing 7 (1971), 281-292.MR 0292344 (45:1431)
33.: M. A. Shokrollahi and V. Stemann, Approximation of Complex Numbers by Cyclotomic Integers, Technical Report TR-96-033, International Computer Science Institute, Berkeley, September 1996.
34.: C. L. Siegel, Über die Classenzahl quadratischer Zahlkörper, Acta Arith. 1 (1935), 83-86.
35.: D. Stehle and P. Zimmermann, A Binary Recursive GCD Algorithm, Proceedings of the Sixth International Algorithmic Number Theory Symposium ANTS VI (Burlington, VT, June 13-18, 2004) D. Buell, ed., Lecture Notes in Comput. Sci., vol. 3076, Springer-Verlag, Berlin, 2004, pp. 411-425.
36.: J. Stein, Computational Problems Associated with Racah Algebra, J. Comput. Phys. 1 (1967), 397-405.
37.: J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge University Press, New York, 1999. MR 1689167 (2000j:68205)
38.: A. Weilert, -ary GCD Computation in $\mathbf{Z}[i]$ as an Analogue to the Binary GCD Algorithm, J. Symbolic Comput. 30 (2000), 605-617. MR 1797272 (2001k:11265)
39.: -, Asymptotically Fast GCD Computation in $\mathbf{Z}[i]$ , Proceedings of the Fourth International Algorithmic Number Theory Symposium ANTS IV (Leiden, The Netherlands, July 2-7, 2000) W. Bosma, ed., Lecture Notes in Comput. Sci., vol. 1838, Springer-Verlag, Berlin, 2000, pp. 595-613. MR 1850636 (2002k:11226)
40.: -, Effiziente Algorithmen zur Berechnung von Idealsummen in quadratischen Ordnungen, Dissertation, Mathematisch-Naturwissenschaftliche Fakultät der Rheinischen-Friedrich-Wilhelms Universität Bonn, Juli 2000.
41.: -, Fast Computation of the Biquadratic Residue Symbol, J. Number Theory 96 (2002), 133-151. MR 1931197 (2003j:11006)

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

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
Email: andre@weilert.de

DOI: 10.1090/S0025-5718-05-01799-0
PII: S 0025-5718(05)01799-0
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.
Posted: 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).
Copyright of article: Copyright 2005, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS