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

Scheidler, R.; Stein, A.

doi:10.1090/S0025-5718-99-01136-9

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
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
Posted: March 11, 1999
MathSciNet review: 1653974
Full-text PDF Free Access

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.

1. J. A. Buchmann, A generalization of Voronoi's algorithm I, II. J. Number Theory 20 (1985), 177-209. MR 86g:11062a,b
2. Johannes Buchmann, The computation of the fundamental unit of totally complex quartic orders, Math. Comp. 48 (1987), no. 177, 39–54. MR 866097 (87m:11126), http://dx.doi.org/10.1090/S0025-5718-1987-0866097-1
3. Johannes Buchmann, On the computation of units and class numbers by a generalization of Lagrange’s algorithm, J. Number Theory 26 (1987), no. 1, 8–30. MR 883530 (89b:11104), http://dx.doi.org/10.1016/0022-314X(87)90092-8
4. Johannes Buchmann, On the period length of the generalized Lagrange algorithm, J. Number Theory 26 (1987), no. 1, 31–37. MR 883531 (88g:11078), http://dx.doi.org/10.1016/0022-314X(87)90093-X
5. J. A. Buchmann, Zur Komplexität der Berechnung von Einheiten und Klassenzahlen algebraischer Zahlkörper. Habilitationsschrift, Universität Düsseldorf, Germany 1987.
6. Johannes Buchmann and H. 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 (89g:11098), http://dx.doi.org/10.1090/S0025-5718-1988-0929554-6
7. B. N. Delone and D. K. Faddeev, The theory of irrationalities of the third degree, Translations of Mathematical Monographs, Vol. 10, American Mathematical Society, Providence, R.I., 1964. MR 0160744 (28 #3955)
8. Max Deuring, Lectures on the theory of algebraic functions of one variable, Lecture Notes in Mathematics, Vol. 314, Springer-Verlag, Berlin, 1973. MR 0344231 (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 and H. Zassenhaus, Algorithmic algebraic number theory, Encyclopedia of Mathematics and its Applications, vol. 30, Cambridge University Press, Cambridge, 1997. Revised reprint of the 1989 original. MR 1483321 (98f:11111)
12. F. K. Schmidt, Analytische Zahlentheorie in Körpern der Charakteristik $p$ . Math. Zeitschrift 33 (1931), 1-32.
13. Daniel Shanks, The infrastructure of a real quadratic field and its applications, Proceedings of the Number Theory Conference (Univ. Colorado, Boulder, Colo., 1972), Univ. Colorado, Boulder, Colo., 1972, pp. 217–224. MR 0389842 (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. Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961 (94k:14016)
17. G. F. Voronoi, On a Generalization of the Algorithm of Continued Fractions (in Russian). Doctoral Dissertation, Warsaw 1896.
18. Bosco Weis and Horst G. Zimmer, Artins Theorie der quadratischen Kongruenzfunktionenkörper und ihre Anwendung auf die Berechnung der Einheiten- und Klassengruppen, Mitt. Math. Ges. Hamburg 12 (1991), no. 2, 261–286 (German). Mathematische Wissenschaften gestern und heute. 300 Jahre Mathematische Gesellschaft in Hamburg, Teil 2. MR 1144788 (93e:11141)
19. Hugh C. Williams, Continued fractions and number-theoretic computations, Rocky Mountain J. Math. 15 (1985), no. 2, 621–655. Number theory (Winnipeg, Man., 1983). MR 823273 (87h:11129), http://dx.doi.org/10.1216/RMJ-1985-15-2-621
20. H. C. Williams, G. Cormack, and E. Seah, Calculation of the regulator of a pure cubic field, Math. Comp. 34 (1980), no. 150, 567–611. MR 559205 (81d:12003), http://dx.doi.org/10.1090/S0025-5718-1980-0559205-7
21. H. C. Williams, G. W. Dueck, and B. K. Schmid, A rapid method of evaluating the regulator and class number of a pure cubic field, Math. Comp. 41 (1983), no. 163, 235–286. MR 701638 (84m:12010), http://dx.doi.org/10.1090/S0025-5718-1983-0701638-2
22. H. C. Williams and M. C. Wunderlich, On the parallel generation of the residues for the continued fraction factoring algorithm, Math. Comp. 48 (1987), no. 177, 405–423. MR 866124 (88i:11099), http://dx.doi.org/10.1090/S0025-5718-1987-0866124-1

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|