Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Voronoi's algorithm
in purely cubic congruence function fields
of unit rank 1


Authors: R. Scheidler and A. Stein
Journal: Math. Comp. 69 (2000), 1245-1266
MSC (1991): Primary 11R16, 11R27; Secondary 11R58, 11-04
DOI: https://doi.org/10.1090/S0025-5718-99-01136-9
Published electronically: March 11, 1999
MathSciNet review: 1653974
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The first part of this paper classifies all purely cubic function fields over a finite field of characteristic not equal to 3. In the remainder, we describe a method for computing the fundamental unit and regulator of a purely cubic congruence function field of unit rank 1 and characteristic at least 5. The technique is based on Voronoi's algorithm for generating a chain of successive minima in a multiplicative cubic lattice, which is used for calculating the fundamental unit and regulator of a purely cubic number field.


References [Enhancements On Off] (What's this?)

  • 1. J. A. Buchmann, A generalization of Voronoi's algorithm I, II. J. Number Theory 20 (1985), 177-209. MR 86g:11062a,b
  • 2. J. A. Buchmann, The computation of the fundamental unit of totally complex quartic orders. Math. Comp. 48 (1987), 39-54. MR 87m:11126
  • 3. J. A. Buchmann, On the computation of units and class numbers by a generalization of Lagrange's algorithm. J. Number Theory 26 (1987), 8-30. MR 89b:11104
  • 4. J. A. Buchmann, On the period length of the generalized Lagrange algorithm. J. Number Theory 26 (1987), 31-37. MR 88g:11078
  • 5. J. A. Buchmann, Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper. Habilitationsschrift, Universität Düsseldorf, Germany 1987.
  • 6. J. A. Buchmann & H. C. Williams, On the infrastructure of the principal ideal class of an algebraic number field of unit rank one. Math. Comp. 50 (1988), 569-579. MR 89g:11098
  • 7. B. N. Delone & D. K. Faddeev, The Theory of Irrationalities of the Third Degree. Transl. Math. Monographs 10, Amer. Math. Soc., Providence, Rhode Island 1964. MR 28:3955
  • 8. M. Deuring, Lectures on the Theory of Algebraic Functions in One Variable. Lect. Notes in Math. 314, Springer, Berlin 1973. MR 49:8970
  • 9. E. Jung, Theorie der Algebraischen Funktionen einer Veränderlichen. Berlin 1923.
  • 10. M. Mang, Berechnung von Fundamentaleinheiten in algebraischen, insbesondere rein-kubischen Kongruenzfunktionenkörpern. Diplomarbeit, Universität des Saarlandes, Saarbrücken, Germany 1987.
  • 11. M. Pohst & H. Zassenhaus, Algorithmic Algebraic Number Theory. Cambridge University Press, 1st paperback ed., Cambridge 1997. MR 98f:11111
  • 12. F. K. Schmidt, Analytische Zahlentheorie in Körpern der Charakteristik $p$. Math. Zeitschrift 33 (1931), 1-32.
  • 13. D. Shanks, The infrastructure of a real quadratic field and its applications. Proc. 1972 Number Theory Conf., Boulder, Colorado 1972, 217-224. MR 52:10672
  • 14. A. Stein, Baby Step-Giant Step-Verfahren in reell-quadratischen Kongruenzfunktionenkörpern mit Charakteristik ungleich 2. Diplomarbeit, Universität des Saarlandes, Saarbrücken, Germany 1992.
  • 15. A. Stein & H. C. Williams, Some methods for evaluating the regulator of a real quadratic function field. To appear in Exp. Math.
  • 16. H. Stichtenoth, Algebraic Function Fields and Codes. Springer, Berlin 1993. MR 94k:14016
  • 17. G. F. Voronoi, On a Generalization of the Algorithm of Continued Fractions (in Russian). Doctoral Dissertation, Warsaw 1896.
  • 18. B. Weis & H. G. Zimmer, Artins Theorie der quadratischen Kongruenzfunktionenkörper und ihre Anwendung auf die Berechnung der Einheiten- und Klassengruppen. Mitt. Math. Ges. Hamburg XII (1991), 261-286. MR 93e:11141
  • 19. H. C. Williams, Continued fractions and number-theoretic computations. Rocky Mountain J. Math. 15 (1985), 621-655. MR 87h:11129
  • 20. H. C. Williams, G. Cormack & E. Seah, Calculation of the regulator of a pure cubic field. Math. Comp. 34 (1980), 567-611. MR 81d:12003
  • 21. H. C. Williams, G. W. Dueck & B. K. Schmid, A rapid method of evaluating the regulator and class number of a pure cubic field. Math. Comp. 41 (1983), 235-286. MR 84m:12010
  • 22. H. C. Williams & M. C. Wunderlich, On the parallel generation of the residues for the continued fraction algorithm. Math. Comp. 48 (1987), 405-423. MR 88i:11099

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (1991): 11R16, 11R27, 11R58, 11-04

Retrieve articles in all journals with MSC (1991): 11R16, 11R27, 11R58, 11-04


Additional Information

R. Scheidler
Affiliation: Department of Mathematical Sciences, University of Delaware, Newark, DE 19716
Email: scheidle@math.udel.edu

A. Stein
Affiliation: Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, CANADA
Email: astein@cacr.math.uwaterloo.ca

DOI: https://doi.org/10.1090/S0025-5718-99-01136-9
Keywords: Purely cubic function field, Voronoi's algorithm, minimum, reduced ideal, fundamental unit, regulator
Received by editor(s): March 31, 1998
Received by editor(s) in revised form: August 14, 1998
Published electronically: March 11, 1999
Additional Notes: The first author was supported by NSF grant DMS-9631647.
Article copyright: © Copyright 2000 American Mathematical Society

American Mathematical Society