{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T15:36:02Z","timestamp":1776785762315,"version":"3.51.2"},"reference-count":41,"publisher":"American Mathematical Society (AMS)","issue":"254","license":[{"start":{"date-parts":[[2006,12,8]],"date-time":"2006-12-08T00:00:00Z","timestamp":1165536000000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"

\n 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\n \n \n \n \n Z<\/mml:mi>\n <\/mml:mrow>\n \\mathbf {Z}<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n up to a constant factor, i.e., in\n \n \n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u03bc\n \n <\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n log<\/mml:mi>\n \n \u2061\n \n <\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n ,<\/mml:mo>\n <\/mml:mrow>\n O(\\mu (n) \\log n),<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n where\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n bounds the size of the operands and\n \n \n \n \n \n \u03bc\n \n <\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \\mu (n)<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n denotes an upper bound for the multiplication time of\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -bit integers. Using Sch\u00f6nhage\u2013Strassen\u2019s asymptotically fast multiplication for\n \n \n \n n<\/mml:mi>\n n<\/mml:annotation>\n <\/mml:semantics>\n <\/mml:math>\n <\/inline-formula>\n -bit integers, we achieve \ud835\udf07(\ud835\udc5b)=\ud835\udc42(\ud835\udc5blog\ud835\udc5bloglog\ud835\udc5b).\n <\/p>","DOI":"10.1090\/s0025-5718-05-01799-0","type":"journal-article","created":{"date-parts":[[2006,2,15]],"date-time":"2006-02-15T11:05:20Z","timestamp":1140001520000},"page":"941-981","source":"Crossref","is-referenced-by-count":0,"title":["Two efficient algorithms for the computation of ideal sums in quadratic orders"],"prefix":"10.1090","volume":"75","author":[{"given":"Andr\u00e9","family":"Weilert","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2005,12,8]]},"reference":[{"key":"1","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0999-7","volume-title":"Modular functions and Dirichlet series in number theory","volume":"41","author":"Apostol, Tom M.","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/0387971270","edition":"2"},{"key":"2","doi-asserted-by":"publisher","first-page":"243","DOI":"10.2307\/2371849","article-title":"On the zeta-functions of algebraic number fields","volume":"69","author":"Brauer, Richard","year":"1947","journal-title":"Amer. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9327","issn-type":"print"},{"key":"3","doi-asserted-by":"publisher","first-page":"739","DOI":"10.2307\/2372290","article-title":"On the zeta-functions of algebraic number fields. II","volume":"72","author":"Brauer, Richard","year":"1950","journal-title":"Amer. J. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9327","issn-type":"print"},{"key":"4","isbn-type":"print","first-page":"159","article-title":"Short representation of quadratic integers","author":"Buchmann, Johannes","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/0792335015"},{"key":"5","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4542-1","volume-title":"Binary quadratic forms","author":"Buell, Duncan A.","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0387970371"},{"key":"6","unstructured":"B. F. Caviness, A Lehmer-Type Greatest Common Divisor Algorithm for Gaussian Integers, SIAM Rev. 15 (1973), no. 2, 414."},{"key":"7","doi-asserted-by":"crossref","unstructured":"B. F. Caviness and G. E. Collins, Algorithms for Gaussian Integer Arithmetic, Proceedings of the 1976 ACM Symposium on Symbolic and Algebraic Computation SYMSAC\u201976 (Yorktown Heights) (R. D. Jenks, ed.), 1976, pp. 36\u201345.","DOI":"10.1145\/800205.806321"},{"key":"8","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02945-9","volume-title":"A course in computational algebraic number theory","volume":"138","author":"Cohen, Henri","year":"1993","ISBN":"https:\/\/id.crossref.org\/isbn\/3540556400"},{"issue":"216","key":"9","doi-asserted-by":"publisher","first-page":"1681","DOI":"10.1090\/S0025-5718-96-00766-1","article-title":"Hermite and Smith normal form algorithms over Dedekind domains","volume":"65","author":"Cohen, Henri","year":"1996","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"10","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8489-0","volume-title":"Advanced topics in computational number theory","volume":"193","author":"Cohen, Henri","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0387987274"},{"issue":"4","key":"11","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1006\/jsco.2001.0518","article-title":"A fast Euclidean algorithm for Gaussian integers","volume":"33","author":"Collins, George E.","year":"2002","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"12","volume-title":"Untersuchungen \\\"{u}ber h\\\"{o}here Arithmetik","author":"Gauss, Carl Friedrich","year":"1965"},{"issue":"6","key":"13","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.1137\/0220067","article-title":"Asymptotically fast triangularization of matrices over rings","volume":"20","author":"Hafner, James L.","year":"1991","journal-title":"SIAM J. Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0097-5397","issn-type":"print"},{"key":"14","volume-title":"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","author":"Euclid","year":"1956"},{"key":"15","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2103-4","volume-title":"A classical introduction to modern number theory","volume":"84","author":"Ireland, Kenneth","year":"1990","ISBN":"https:\/\/id.crossref.org\/isbn\/038797329X","edition":"2"},{"key":"16","isbn-type":"print","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/3-540-15984-3_278","article-title":"Arithmetic in quadratic fields with unique factorization","author":"Kaltofen, Erich","year":"1985","ISBN":"https:\/\/id.crossref.org\/isbn\/3540159843"},{"issue":"188","key":"17","doi-asserted-by":"publisher","first-page":"697","DOI":"10.2307\/2008732","article-title":"Computing greatest common divisors and factorizations in quadratic number fields","volume":"53","author":"Kaltofen, Erich","year":"1989","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"key":"18","first-page":"269","article-title":"The analysis of algorithms","author":"Knuth, Donald E.","year":"1971"},{"key":"19","series-title":"Addison-Wesley Series in Computer Science and Information Processing","isbn-type":"print","volume-title":"The art of computer programming. Vol. 2","author":"Knuth, Donald E.","year":"1981","ISBN":"https:\/\/id.crossref.org\/isbn\/0201038226","edition":"2"},{"key":"20","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0041-0","volume-title":"Algebra","volume":"211","author":"Lang, Serge","year":"2002","ISBN":"https:\/\/id.crossref.org\/isbn\/038795385X","edition":"3"},{"key":"21","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0853-2","volume-title":"Algebraic number theory","volume":"110","author":"Lang, Serge","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/0387942254","edition":"2"},{"key":"22","doi-asserted-by":"crossref","unstructured":"D. H. Lehmer, Euclid\u2019s Algorithm for Large Numbers, Amer. Math. Monthly 45 (1938), 227\u2013233.","DOI":"10.1080\/00029890.1938.11990797"},{"issue":"5","key":"23","first-page":"385","article-title":"The Euclidean algorithm in algebraic number fields","volume":"13","author":"Lemmermeyer, Franz","year":"1995","journal-title":"Exposition. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0723-0869","issn-type":"print"},{"key":"24","isbn-type":"print","first-page":"123","article-title":"On the calculation of regulators and class numbers of quadratic fields","author":"Lenstra, H. W., Jr.","year":"1982","ISBN":"https:\/\/id.crossref.org\/isbn\/0521285135"},{"key":"25","isbn-type":"print","volume-title":"Introduction to algorithms","author":"Manber, Udi","year":"1989","ISBN":"https:\/\/id.crossref.org\/isbn\/0201120372"},{"key":"26","series-title":"Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03983-0","volume-title":"Algebraic number theory","volume":"322","author":"Neukirch, J\u00fcrgen","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3540653996"},{"key":"27","series-title":"Graduate Texts in Mathematics","isbn-type":"print","volume-title":"Analytic number theory","volume":"177","author":"Newman, Donald J.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/0387983082"},{"key":"28","doi-asserted-by":"crossref","unstructured":"A. Sch\u00f6nhage, Schnelle Berechnung von Kettenbruchentwicklungen, Acta Inform. 1 (1971), 139\u2013144.","DOI":"10.1007\/BF00289520"},{"key":"29","unstructured":"\\bysame, IGCDOC, Computation of Integer GCD\u2019s, Unpublished Manuscript, 1987."},{"key":"30","doi-asserted-by":"crossref","unstructured":"\\bysame, Fast Reduction and Composition of Binary Quadratic Forms, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation ISSAC\u201991 (Bonn, Germany, July 15\u201317, 1991) S. M. Watt, ed., ACM Press, New York, 1991, pp. 128\u2013133.","DOI":"10.1145\/120694.120711"},{"key":"31","isbn-type":"print","volume-title":"Fast algorithms","author":"Sch\u00f6nhage, Arnold","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3411168919"},{"key":"32","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/bf02242355","article-title":"Schnelle Multiplikation grosser Zahlen","volume":"7","author":"Sch\u00f6nhage, A.","year":"1971","journal-title":"Computing (Arch. Elektron. Rechnen)","ISSN":"https:\/\/id.crossref.org\/issn\/0010-485X","issn-type":"print"},{"key":"33","unstructured":"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."},{"key":"34","doi-asserted-by":"crossref","unstructured":"C. L. Siegel, \u00dcber die Classenzahl quadratischer Zahlk\u00f6rper, Acta Arith. 1 (1935), 83\u201386.","DOI":"10.4064\/aa-1-1-83-86"},{"key":"35","unstructured":"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\u201318, 2004) D. Buell, ed., Lecture Notes in Comput. Sci., vol. 3076, Springer-Verlag, Berlin, 2004, pp. 411\u2013425."},{"key":"36","doi-asserted-by":"crossref","unstructured":"J. Stein, Computational Problems Associated with Racah Algebra, J. Comput. Phys. 1 (1967), 397\u2013405.","DOI":"10.1016\/0021-9991(67)90047-2"},{"key":"37","isbn-type":"print","volume-title":"Modern computer algebra","author":"von zur Gathen, Joachim","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/0521641764"},{"issue":"5","key":"38","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1006\/jsco.2000.0422","article-title":"(1+\ud835\udc56)-ary GCD computation in \ud835\udc4d[\ud835\udc56] is an analogue to the binary GCD algorithm","volume":"30","author":"Weilert, Andr\u00e9","year":"2000","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"39","isbn-type":"print","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/10722028_40","article-title":"Asymptotically fast GCD computation in \u2124[\ud835\udd5a]","author":"Weilert, Andr\u00e9","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/3540676953"},{"key":"40","unstructured":"\\bysame, Effiziente Algorithmen zur Berechnung von Idealsummen in quadratischen Ordnungen, Dissertation, Mathematisch-Naturwissenschaftliche Fakult\u00e4t der Rheinischen-Friedrich-Wilhelms Universit\u00e4t Bonn, Juli 2000."},{"issue":"1","key":"41","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0022-314X(02)92783-6","article-title":"Fast computation of the biquadratic residue symbol","volume":"96","author":"Weilert, Andr\u00e9","year":"2002","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-05-01799-0\/S0025-5718-05-01799-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-05-01799-0\/S0025-5718-05-01799-0.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:35:49Z","timestamp":1776782149000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2006-75-254\/S0025-5718-05-01799-0\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12,8]]},"references-count":41,"journal-issue":{"issue":"254","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["S0025-5718-05-01799-0"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-05-01799-0","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2005,12,8]]}}}