A Terr algorithm for computations in the infrastructure of real-quadratic number fields
Journal de Théorie des Nombres de Bordeaux, Tome 18 (2006) no. 3, pp. 559-572.

Nous montrons comment adapter la variante due à Terr de l’algorithme “baby-step giant-step” de Shanks pour le calcul du régulateur et des générateurs des idéaux principaux des corps quadratiques réels. La complexité du pire cas de l’algorithme obtenu dépend uniquement de la racine carrée du régulateur, et est plus petite que toutes celles des algorithmes inconditionnels et déterministes connus précédemment pour ce problème.

We show how to adapt Terr’s variant of the baby-step giant-step algorithm of Shanks to the computation of the regulator and of generators of principal ideals in real-quadratic number fields. The worst case complexity of the resulting algorithm depends only on the square root of the regulator, and is smaller than that of all other previously specified unconditional deterministic algorithm for this task.

@article{JTNB_2006__18_3_559_0,
     author = {Buchmann, Johannes and Volmer, Ulrich},
     title = {A Terr algorithm for computations in the infrastructure of real-quadratic number fields},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {559--572},
     publisher = {Universit\'e Bordeaux 1},
     volume = {18},
     number = {3},
     year = {2006},
     doi = {10.5802/jtnb.558},
     mrnumber = {2330427},
     zbl = {1132.11055},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/jtnb.558/}
}
Buchmann, Johannes; Volmer, Ulrich. A Terr algorithm for computations in the infrastructure of real-quadratic number fields. Journal de Théorie des Nombres de Bordeaux, Tome 18 (2006) no. 3, pp. 559-572. doi : 10.5802/jtnb.558. http://www.numdam.org/articles/10.5802/jtnb.558/

[Bac90] Eric Bach, Explicit bounds for primality testing and related problems. Mathematics of Computation 55 (1990), no. 191, 355–380. | MR 1023756 | Zbl 0701.11075

[BB99] Ingrid Biehl, Johannes Buchmann, An analysis of the reduction algorithms for binary quadratic forms. In Peter Engel and Halyna M. Syta, editors, Voronoi’s Impact on Modern Science, Kyiv, Ukraine 1998, pages 71–98. National Academy of Sciences of Ukraine, 1999. | Zbl 0948.11051

[BJT97] Johannes Buchmann, Michael J. Jacobson, Jr., Edlyn Teske, On some computational problems in finite abelian groups. Math. Comp. 66 (1997), no. 220, 1663–1687. | MR 1432126 | Zbl 0894.11050

[BS05] Johannes Buchmann, Arthur Schmidt, Computing the structure of a finite abelian group. Mathematics of Computation 74 (2005), no. 252, 2017–2026. | MR 2164109 | Zbl 1089.20032

[BV07] Johannes Buchmann, Ulrich Vollmer Binary Quadratic Forms – An Algorithmic Approach. Algorithms and Computation in Mathematics, vol. 20. Springer 2007. | MR 2300780 | Zbl 05136071

[BW88] Johannes Buchmann, Hugh C. Williams, On the infrastructure of the principal ideal class of an algebraic number field of unit rank one. Math. Comp. 50 (1988), no. 182, 569–579. | MR 929554 | Zbl 0653.12005

[Len82] Hendrik W. Lenstra, Jr., On the calculation of regulators and class numbers of quadratic fields. In J. V. Armitage, editor, Journees Arithmetiques, Exeter 1980, London Mathematical Society Lecture Notes Series, vol. 56, pages 123–150. Cambridge University Press, 1982. | MR 697260 | Zbl 0487.12003

[Sch04] René Schoof, Computing Arakelov class groups. http://axp.mat.uniroma2.it/~schoof/infranew2.pdf, October 2004.

[Sha71] Daniel Shanks, Class number, a theory of factorization, and genera. In 1969 Number Theory Institute (Proc. Sympos. Pure Math., Vol. XX, State Univ. New York, Stony Brook, N.Y., 1969), pages 415–440. Amer. Math. Soc., Providence, R.I., 1971. | MR 316385 | Zbl 0223.12006

[Ter00] David C. Terr A modification of Shanks’ baby-step giant-step algorithm. Mathematics of Computation 69 (2000), no. 230, 767–773. | Zbl 0940.68038

[Vol03] Ulrich Vollmer, Rigorously Analyzed Algorithms for the Discrete Logarithm Problem in Quadratic Number Fields. PhD thesis, Technische Universität Darmstadt, Fachbereich Informatik, 2003.