A Terr algorithm for computations in the infrastructure of real-quadratic number fields

Johannes Buchmann[1]; Ulrich Volmer[1]

  • [1] Technische Universität Darmstadt Department of Computer Science Hochschulstr. 10, 64289 Darmstadt, Germany

Journal de Théorie des Nombres de Bordeaux (2006)

  • Volume: 18, Issue: 3, page 559-572
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Buchmann, Johannes, and Volmer, Ulrich. "A Terr algorithm for computations in the infrastructure of real-quadratic number fields." Journal de Théorie des Nombres de Bordeaux 18.3 (2006): 559-572. <http://eudml.org/doc/249657>.

@article{Buchmann2006,
abstract = {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.},
affiliation = {Technische Universität Darmstadt Department of Computer Science Hochschulstr. 10, 64289 Darmstadt, Germany; Technische Universität Darmstadt Department of Computer Science Hochschulstr. 10, 64289 Darmstadt, Germany},
author = {Buchmann, Johannes, Volmer, Ulrich},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {infrastructure; real quadratic fields; Terr algorithm},
language = {eng},
number = {3},
pages = {559-572},
publisher = {Université Bordeaux 1},
title = {A Terr algorithm for computations in the infrastructure of real-quadratic number fields},
url = {http://eudml.org/doc/249657},
volume = {18},
year = {2006},
}

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
PB - Université Bordeaux 1
VL - 18
IS - 3
SP - 559
EP - 572
AB - 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.
LA - eng
KW - infrastructure; real quadratic fields; Terr algorithm
UR - http://eudml.org/doc/249657
ER -

References

top
  1. Eric Bach, Explicit bounds for primality testing and related problems. Mathematics of Computation 55 (1990), no. 191, 355–380. Zbl0701.11075MR1023756
  2. 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. Zbl0948.11051
  3. Johannes Buchmann, Michael J. Jacobson, Jr., Edlyn Teske, On some computational problems in finite abelian groups. Math. Comp. 66 (1997), no. 220, 1663–1687. Zbl0894.11050MR1432126
  4. Johannes Buchmann, Arthur Schmidt, Computing the structure of a finite abelian group. Mathematics of Computation 74 (2005), no. 252, 2017–2026. Zbl1089.20032MR2164109
  5. Johannes Buchmann, Ulrich VollmerBinary Quadratic Forms – An Algorithmic Approach. Algorithms and Computation in Mathematics, vol. 20. Springer 2007. Zbl1125.11028MR2300780
  6. 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. Zbl0653.12005MR929554
  7. 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. Zbl0487.12003MR697260
  8. René Schoof, Computing Arakelov class groups. http://axp.mat.uniroma2.it/~schoof/infranew2.pdf, October 2004. Zbl1188.11076
  9. 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. Zbl0223.12006MR316385
  10. David C. TerrA modification of Shanks’ baby-step giant-step algorithm. Mathematics of Computation 69 (2000), no. 230, 767–773. Zbl0940.68038
  11. Ulrich Vollmer, Rigorously Analyzed Algorithms for the Discrete Logarithm Problem in Quadratic Number Fields. PhD thesis, Technische Universität Darmstadt, Fachbereich Informatik, 2003. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.