The infrastructure of a global field of arbitrary unit rank

Fontein, Felix

doi:10.1090/S0025-5718-2011-02490-7

The infrastructure of a global field of arbitrary unit rank
HTML articles powered by AMS MathViewer

by Felix Fontein PDF

Math. Comp. 80 (2011), 2325-2357

Abstract:

In this paper, we show a general way to interpret the infrastructure of a global field of arbitrary unit rank. This interpretation generalizes the prior concepts of the giant-step operation and $f$-representations, and makes it possible to relate the infrastructure to the (Arakelov) divisor class group of the global field. In the case of global function fields, we present results that establish that effective implementation of the presented methods is indeed possible, and we show how Shanks’ baby-step giant-step method can be generalized to this situation.

References

H. Appelgate and H. Onishi, Periodic expansion of modules and its relation to units, J. Number Theory 15 (1982), no. 3, 283–294. MR 680533, DOI 10.1016/0022-314X(82)90033-6
Yvo G. Desmedt (ed.), Advances in cryptology—CRYPTO ’94, Lecture Notes in Computer Science, vol. 839, Springer-Verlag, Berlin, 1994. MR 1316402
Gunter Bergmann, Theorie der Netze, Math. Ann. 149 (1963), 361–418 (German). MR 157948, DOI 10.1007/BF01397976
Johannes Buchmann and Arthur Schmidt, Computing the structure of a finite abelian group, Math. Comp. 74 (2005), no. 252, 2017–2026. MR 2164109, DOI 10.1090/S0025-5718-05-01740-0
Johannes Buchmann, A generalization of Voronoĭ’s unit algorithm. I, J. Number Theory 20 (1985), no. 2, 177–191. MR 790781, DOI 10.1016/0022-314X(85)90039-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, DOI 10.1016/0022-314X(87)90092-8
—, Zur Komplexität der Berechnung von Einheiten und Klassenzahl algebraischer Zahlkörper, Habilitationsschrift, October 1987.
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, DOI 10.1090/S0025-5718-1988-0929554-6
Johannes A. Buchmann and Hugh C. Williams, A key exchange system based on real quadratic fields (extended abstract), Advances in cryptology—CRYPTO ’89 (Santa Barbara, CA, 1989) Lecture Notes in Comput. Sci., vol. 435, Springer, New York, 1990, pp. 335–343. MR 1062244, DOI 10.1007/0-387-34805-0_{3}1
Henri Cohen, Gerhard Frey, Roberto Avanzi, Christophe Doche, Tanja Lange, Kim Nguyen, and Frederik Vercauteren (eds.), Handbook of elliptic and hyperelliptic curve cryptography, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2006. MR 2162716
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
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
Felix Fontein, Groups from cyclic infrastructures and Pohlig-Hellman in certain infrastructures, Adv. Math. Commun. 2 (2008), no. 3, 293–307. MR 2429459, DOI 10.3934/amc.2008.2.293
F. Fontein, The infrastructure of a global field and baby step-giant step algorithms, Ph.D. thesis, Universität Zürich, March 2009, http://user.math.uzh.ch/ fontein/diss-fontein.pdf.
Steven D. Galbraith, Michael Harrison, and David J. Mireles Morales, Efficient hyperelliptic arithmetic using balanced representation for divisors, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 342–356. MR 2467851, DOI 10.1007/978-3-540-79456-1_{2}3
S. D. Galbraith, S. M. Paulus, and N. P. Smart, Arithmetic on superelliptic curves, Math. Comp. 71 (2002), no. 237, 393–405. MR 1863009, DOI 10.1090/S0025-5718-00-01297-7
F. Heß, Zur Divisorklassengruppenberechnung in globalen funktionenkörpern, Ph.D. thesis, Technische Universität Berlin, 1999.
F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425–445. MR 1890579, DOI 10.1006/jsco.2001.0513
Y. Hellegouarch and R. Paysant-Le Roux, Commas, points extrémaux et arêtes des corps possédant une formule du produit, C. R. Math. Rep. Acad. Sci. Canada 7 (1985), no. 5, 291–296 (French, with English summary). MR 813946
Y. Hellegouarch and R. Paysant-Le Roux, Invariants arithmétiques des corps possédant une formule du produit; applications, Astérisque 147-148 (1987), 291–300, 345 (French). Journées arithmétiques de Besançon (Besançon, 1985). MR 891435
Detlef Hühnlein and Sachar Paulus, On the implementation of cryptosystems based on real quadratic number fields (extended abstract), Selected areas in cryptography (Waterloo, ON, 2000) Lecture Notes in Comput. Sci., vol. 2012, Springer, Berlin, 2001, pp. 288–302. MR 1895598, DOI 10.1007/3-540-44983-3_{2}1
M. J. Jacobson, Jr., Subexponential class group computation in quadratic orders, Ph.D. thesis, Technische Universität Darmstadt, 1999.
M. J. Jacobson, R. Scheidler, and A. Stein, Cryptographic protocols on real hyperelliptic curves, Adv. Math. Commun. 1 (2007), no. 2, 197–221. MR 2306309, DOI 10.3934/amc.2007.1.197
Michael J. Jacobson Jr., Renate Scheidler, and Hugh C. Williams, The efficiency and security of a real quadratic field based key exchange protocol, Public-key cryptography and computational number theory (Warsaw, 2000) de Gruyter, Berlin, 2001, pp. 89–112. MR 1881630
Michael J. Jacobson Jr., Renate Scheidler, and Hugh C. Williams, An improved real-quadratic-field-based key exchange procedure, J. Cryptology 19 (2006), no. 2, 211–239. MR 2213407, DOI 10.1007/s00145-005-0357-6
E. Landquist, Infrastructure, Arithmetic, and Class Number Computations in Purely Cubic Function Fields of Characteristic at Least $5$, Ph.D. thesis, University of Illinois at Urbana-Champaign, 2009, http://www.math.uiuc.edu/~landquis/articles/ landquist-thesis.pdf.
H. W. Lenstra, On the computation of regulators and class numbers of quadratic fields, Journées Arithmétiques 1980 (Exeter, 13th–19th April 1980) (Cambridge) (J. V. Armitage, ed.), London Mathematical Society Lecture Notes, no. 56, Cambridge University Press, 1982, pp. 123–150.
Y. Lee, R. Scheidler, and C. Yarrish, Computation of the fundamental units and the regulator of a cyclic cubic function field, Experiment. Math. 12 (2003), no. 2, 211–225. MR 2016707, DOI 10.1080/10586458.2003.10504493
M. Maurer, Regulator approximation and fundamental unit computation for real-quadratic orders, Ph.D. thesis, Technische Universität Darmstadt, 2000.
Volker Müller, Andreas Stein, and Christoph Thiel, Computing discrete logarithms in real quadratic congruence function fields of large genus, Math. Comp. 68 (1999), no. 226, 807–822. MR 1620235, DOI 10.1090/S0025-5718-99-01040-6
Jürgen Neukirch, Algebraic number theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 322, Springer-Verlag, Berlin, 1999. Translated from the 1992 German original and with a note by Norbert Schappacher; With a foreword by G. Harder. MR 1697859, DOI 10.1007/978-3-662-03983-0
Sachar Paulus and Hans-Georg Rück, Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comp. 68 (1999), no. 227, 1233–1241. MR 1627817, DOI 10.1090/S0025-5718-99-01066-2
Michael Pohst, Peter Weiler, and Hans Zassenhaus, On effective computation of fundamental units. II, Math. Comp. 38 (1982), no. 157, 293–329. MR 637308, DOI 10.1090/S0025-5718-1982-0637308-8
Michael Pohst and Hans Zassenhaus, An effective number geometric method of computing the fundamental units of an algebraic number field, Math. Comp. 31 (1977), no. 139, 754–770. MR 498486, DOI 10.1090/S0025-5718-1977-0498486-5
Michael Pohst and Hans Zassenhaus, On effective computation of fundamental units. I, Math. Comp. 38 (1982), no. 157, 275–291. MR 637307, DOI 10.1090/S0025-5718-1982-0637307-6
Michael Rosen, Number theory in function fields, Graduate Texts in Mathematics, vol. 210, Springer-Verlag, New York, 2002. MR 1876657, DOI 10.1007/978-1-4757-6046-0
Renate Scheidler, Johannes A. Buchmann, and Hugh C. Williams, A key-exchange protocol using real quadratic fields, J. Cryptology 7 (1994), no. 3, 171–199. MR 1286662, DOI 10.1007/BF02318548
R. J. Schoof, Quadratic fields and factorization, Computational methods in number theory, Part II, Math. Centre Tracts, vol. 155, Math. Centrum, Amsterdam, 1982, pp. 235–286. MR 702519
Renate Scheidler, Ideal arithmetic and infrastructure in purely cubic function fields, J. Théor. Nombres Bordeaux 13 (2001), no. 2, 609–631 (English, with English and French summaries). MR 1879675, DOI 10.5802/jtnb.340
R. J. Schoof, Computing Arakelov class groups, MSRI Publications, vol. 44, pp. 447–495, Cambridge University Press, Cambridge, 2008.
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
Renate Scheidler and Andreas Stein, Unit computation in purely cubic function fields of unit rank 1, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 592–606. MR 1726104, DOI 10.1007/BFb0054895
R. Scheidler, A. Stein, and Hugh C. Williams, Key-exchange in real quadratic congruence function fields, Des. Codes Cryptogr. 7 (1996), no. 1-2, 153–174. Special issue dedicated to Gustavus J. Simmons. MR 1377761, DOI 10.1007/BF00125081
Ray Steiner, On the units in algebraic number fields, Proceedings of the Sixth Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1976) Congress. Numer., XVIII, Utilitas Math., Winnipeg, Man., 1977, pp. 413–435. MR 532716
A. Stein, Baby step-giant step-Verfahren in reellquadratischen Kongruenzfunktionenkörpern mit Charakteristik ungleich 2, Diplomarbeit, Universität des Saarlandes, Saarbrücken, 1992.
Andreas Stein, Equivalences between elliptic curves and real quadratic congruence function fields, J. Théor. Nombres Bordeaux 9 (1997), no. 1, 75–95 (English, with English and French summaries). MR 1469663, DOI 10.5802/jtnb.191
Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
Andreas Stein and Hugh C. Williams, An improved method of computing the regulator of a real quadratic function field, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 607–620. MR 1726105, DOI 10.1007/BFb0054896
Andreas Stein and Hugh C. Williams, Some methods for evaluating the regulator of a real quadratic function field, Experiment. Math. 8 (1999), no. 2, 119–133. MR 1700574, DOI 10.1080/10586458.1999.10504394
A. Stein and H. G. Zimmer, An algorithm for determining the regulator and the fundamental unit of hyperelliptic congruence function field, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ISSAC ’91, Bonn, Germany, July 15-17, 1991, Association for Computing Machinery, 1991, pp. 183–184.
Christoph Thiel, Short proofs using compact representations of algebraic integers, J. Complexity 11 (1995), no. 3, 310–329. MR 1349260, DOI 10.1006/jcom.1995.1014
U. Vollmer, Rigorously analyzed algorithms for the discrete logarithm problem in quadratic number fields, Ph.D. thesis, Technische Universität Darmstadt, 2003.
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, DOI 10.1216/RMJ-1985-15-2-621
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, DOI 10.1090/S0025-5718-1987-0866124-1