Two efficient algorithms for the computation of ideal sums in quadratic orders
HTML articles powered by AMS MathViewer
- by André Weilert PDF
- Math. Comp. 75 (2006), 941-981 Request permission
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 𝜇(𝑛)=𝑂(𝑛log𝑛loglog𝑛).References
- Tom M. Apostol, Modular functions and Dirichlet series in number theory, 2nd ed., Graduate Texts in Mathematics, vol. 41, Springer-Verlag, New York, 1990. MR 1027834, DOI 10.1007/978-1-4612-0999-7
- Richard Brauer, On the zeta-functions of algebraic number fields, Amer. J. Math. 69 (1947), 243–250. MR 20597, DOI 10.2307/2371849
- Richard Brauer, On the zeta-functions of algebraic number fields. II, Amer. J. Math. 72 (1950), 739–746. MR 39009, DOI 10.2307/2372290
- Johannes Buchmann, Christoph Thiel, and Hugh Williams, Short representation of quadratic integers, Computational algebra and number theory (Sydney, 1992) Math. Appl., vol. 325, Kluwer Acad. Publ., Dordrecht, 1995, pp. 159–185. MR 1344929
- Duncan A. Buell, Binary quadratic forms, Springer-Verlag, New York, 1989. Classical theory and modern computations. MR 1012948, DOI 10.1007/978-1-4612-4542-1
- B. F. Caviness, A Lehmer-Type Greatest Common Divisor Algorithm for Gaussian Integers, SIAM Rev. 15 (1973), no. 2, 414.
- 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.
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- Henri Cohen, Hermite and Smith normal form algorithms over Dedekind domains, Math. Comp. 65 (1996), no. 216, 1681–1699. MR 1361805, DOI 10.1090/S0025-5718-96-00766-1
- Henri Cohen, Advanced topics in computational number theory, Graduate Texts in Mathematics, vol. 193, Springer-Verlag, New York, 2000. MR 1728313, DOI 10.1007/978-1-4419-8489-0
- George E. Collins, A fast Euclidean algorithm for Gaussian integers, J. Symbolic Comput. 33 (2002), no. 4, 385–392. MR 1890576, DOI 10.1006/jsco.2001.0518
- Carl Friedrich Gauss, Untersuchungen über höhere Arithmetik, Chelsea Publishing Co., New York, 1965 (German). Deutsch herausgegeben von H. Maser. MR 0188045
- James L. Hafner and Kevin S. McCurley, Asymptotically fast triangularization of matrices over rings, SIAM J. Comput. 20 (1991), no. 6, 1068–1083. MR 1135749, DOI 10.1137/0220067
- Euclid, The thirteen books of Euclid’s Elements translated from the text of Heiberg. Vol. I: Introduction and Books I, II. Vol. II: Books III–IX. Vol. III: Books X–XIII and Appendix, Dover Publications, Inc., New York, 1956. Translated with introduction and commentary by Thomas L. Heath; 2nd ed. MR 0075873
- Kenneth Ireland and Michael Rosen, A classical introduction to modern number theory, 2nd ed., Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York, 1990. MR 1070716, DOI 10.1007/978-1-4757-2103-4
- Erich Kaltofen and Heinrich Rolletschek, Arithmetic in quadratic fields with unique factorization, EUROCAL ’85, Vol. 2 (Linz, 1985) Lecture Notes in Comput. Sci., vol. 204, Springer, Berlin, 1985, pp. 279–288. MR 826569, DOI 10.1007/3-540-15984-3_{2}78
- Erich Kaltofen and Heinrich Rolletschek, Computing greatest common divisors and factorizations in quadratic number fields, Math. Comp. 53 (1989), no. 188, 697–720. MR 982367, DOI 10.1090/S0025-5718-1989-0982367-2
- Donald E. Knuth, The analysis of algorithms, Actes du Congrès International des Mathématiciens (Nice, 1970) Gauthier-Villars, Paris, 1971, pp. 269–274. MR 0423865
- Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Serge Lang, Algebra, 3rd ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002. MR 1878556, DOI 10.1007/978-1-4613-0041-0
- Serge Lang, Algebraic number theory, 2nd ed., Graduate Texts in Mathematics, vol. 110, Springer-Verlag, New York, 1994. MR 1282723, DOI 10.1007/978-1-4612-0853-2
- D. H. Lehmer, Euclid’s Algorithm for Large Numbers, Amer. Math. Monthly 45 (1938), 227–233.
- Franz Lemmermeyer, The Euclidean algorithm in algebraic number fields, Exposition. Math. 13 (1995), no. 5, 385–416. MR 1362867
- H. W. Lenstra Jr., On the calculation of regulators and class numbers of quadratic fields, Number theory days, 1980 (Exeter, 1980) London Math. Soc. Lecture Note Ser., vol. 56, Cambridge Univ. Press, Cambridge, 1982, pp. 123–150. MR 697260
- Udi Manber, Introduction to algorithms, Addison-Wesley Publishing Company, Advanced Book Program, Reading, MA, 1989. A creative approach. MR 1091251
- Jürgen Neukirch, Algebraic number theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 322, Springer-Verlag, Berlin, 1999. Translated from the 1992 German original and with a note by Norbert Schappacher; With a foreword by G. Harder. MR 1697859, DOI 10.1007/978-3-662-03983-0
- Donald J. Newman, Analytic number theory, Graduate Texts in Mathematics, vol. 177, Springer-Verlag, New York, 1998. MR 1488421
- A. Schönhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inform. 1 (1971), 139–144.
- —, IGCDOC, Computation of Integer GCD’s, Unpublished Manuscript, 1987.
- —, 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.
- Arnold Schönhage, Andreas F. W. Grotefeld, and Ekkehart Vetter, Fast algorithms, Bibliographisches Institut, Mannheim, 1994. A multitape Turing machine implementation. MR 1290996
- A. Schönhage and V. Strassen, Schnelle Multiplikation grosser Zahlen, Computing (Arch. Elektron. Rechnen) 7 (1971), 281–292 (German, with English summary). MR 292344, DOI 10.1007/bf02242355
- 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.
- C. L. Siegel, Über die Classenzahl quadratischer Zahlkörper, Acta Arith. 1 (1935), 83–86.
- 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.
- J. Stein, Computational Problems Associated with Racah Algebra, J. Comput. Phys. 1 (1967), 397–405.
- Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, Cambridge University Press, New York, 1999. MR 1689167
- André Weilert, $(1+i)$-ary GCD computation in $\textbf {Z}[i]$ is an analogue to the binary GCD algorithm, J. Symbolic Comput. 30 (2000), no. 5, 605–617. MR 1797272, DOI 10.1006/jsco.2000.0422
- André Weilert, Asymptotically fast GCD computation in $\Bbb Z[i]$, Algorithmic number theory (Leiden, 2000) Lecture Notes in Comput. Sci., vol. 1838, Springer, Berlin, 2000, pp. 595–613. MR 1850636, DOI 10.1007/10722028_{4}0
- —, Effiziente Algorithmen zur Berechnung von Idealsummen in quadratischen Ordnungen, Dissertation, Mathematisch-Naturwissenschaftliche Fakultät der Rheinischen-Friedrich-Wilhelms Universität Bonn, Juli 2000.
- André Weilert, Fast computation of the biquadratic residue symbol, J. Number Theory 96 (2002), no. 1, 133–151. MR 1931197, DOI 10.1016/S0022-314X(02)92783-6
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
- Email: andre@weilert.de
- 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).
- © Copyright 2005
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp. 75 (2006), 941-981
- MSC (2000): Primary 54C40, 14E20; Secondary 46E25, 20C20
- DOI: https://doi.org/10.1090/S0025-5718-05-01799-0
- MathSciNet review: 2197002