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},
zbl = {1132.11055},
mrnumber = {2330427},
language = {en},
url = {http://www.numdam.org/articles/10.5802/jtnb.558/}
}
TY - JOUR AU - Buchmann, Johannes AU - Volmer, Ulrich TI - A Terr algorithm for computations in the infrastructure of real-quadratic number fields JO - Journal de théorie des nombres de Bordeaux PY - 2006 SP - 559 EP - 572 VL - 18 IS - 3 PB - Université Bordeaux 1 UR - http://www.numdam.org/articles/10.5802/jtnb.558/ DO - 10.5802/jtnb.558 LA - en ID - JTNB_2006__18_3_559_0 ER -
%0 Journal Article %A Buchmann, Johannes %A Volmer, Ulrich %T A Terr algorithm for computations in the infrastructure of real-quadratic number fields %J Journal de théorie des nombres de Bordeaux %D 2006 %P 559-572 %V 18 %N 3 %I Université Bordeaux 1 %U http://www.numdam.org/articles/10.5802/jtnb.558/ %R 10.5802/jtnb.558 %G en %F JTNB_2006__18_3_559_0
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 | Zbl
[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
[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 | Zbl
[BS05] Johannes Buchmann, Arthur Schmidt, Computing the structure of a finite abelian group. Mathematics of Computation 74 (2005), no. 252, 2017–2026. | MR | Zbl
[BV07] Johannes Buchmann, Ulrich Vollmer Binary Quadratic Forms – An Algorithmic Approach. Algorithms and Computation in Mathematics, vol. 20. Springer 2007. | MR | Zbl
[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 | Zbl
[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 | Zbl
[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 | Zbl
[Ter00] David C. Terr A modification of Shanks’ baby-step giant-step algorithm. Mathematics of Computation 69 (2000), no. 230, 767–773. | Zbl
[Vol03] Ulrich Vollmer, Rigorously Analyzed Algorithms for the Discrete Logarithm Problem in Quadratic Number Fields. PhD thesis, Technische Universität Darmstadt, Fachbereich Informatik, 2003.
Cité par Sources :
