Mathematics of Computation

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



Computing discrete logarithms
in real quadratic congruence function fields
of large genus

Authors: Volker Müller, Andreas Stein and Christoph Thiel
Journal: Math. Comp. 68 (1999), 807-822
MSC (1991): Primary 11Y16, 11R29; Secondary 11T71, 11R58, 68Q25, 94A60
MathSciNet review: 1620235
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The discrete logarithm problem in various finite abelian groups is the basis for some well known public key cryptosystems. Recently, real quadratic congruence function fields were used to construct a public key distribution system. The security of this public key system is based on the difficulty of a discrete logarithm problem in these fields. In this paper, we present a probabilistic algorithm with subexponential running time that computes such discrete logarithms in real quadratic congruence function fields of sufficiently large genus. This algorithm is a generalization of similar algorithms for real quadratic number fields.

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

  • 1. C.S. ABEL, Ein Algorithmus zur Berechnung der Klassenzahl und des Regulators reellquadratischer Ordnungen, PhD Thesis, Universität des Saarlandes, Saarbrücken, (1994).
  • 2. E. ARTIN, Quadratische Körper im Gebiete der höheren Kongruenzen I, II, Math. Zeitschr. 19 (1924), 153-206.
  • 3. Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, 10.1090/S0025-5718-1990-1023756-8
  • 4. Johannes Buchmann, A subexponential algorithm for the determination of class groups and regulators of algebraic number fields, Séminaire de Théorie des Nombres, Paris 1988–1989, Progr. Math., vol. 91, Birkhäuser Boston, Boston, MA, 1990, pp. 27–41. MR 1104698
  • 5. Johannes Buchmann, Christoph Thiel, and Hugh Williams, Short representation of quadratic integers, Computational algebra and number theory (Sydney, 1992) Math. Appl., vol. 325, Kluwer Acad. Publ., Dordrecht, 1995, pp. 159–185. MR 1344929
  • 6. Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206
  • 7. Max Deuring, Lectures on the theory of algebraic functions of one variable, Lecture Notes in Mathematics, Vol. 314, Springer-Verlag, Berlin-New York, 1973. MR 0344231
  • 8. P. D. Domich, R. Kannan, and L. E. Trotter Jr., Hermite normal form computation using modulo determinant arithmetic, Math. Oper. Res. 12 (1987), no. 1, 50–59. MR 882842, 10.1287/moor.12.1.50
  • 9. Martin Eichler, Introduction to the theory of algebraic numbers and functions, Translated from the German by George Striker. Pure and Applied Mathematics, Vol. 23, Academic Press, New York-London, 1966. MR 0209258
  • 10. Daniel M. Gordon, Discrete logarithms in 𝐺𝐹(𝑝) using the number field sieve, SIAM J. Discrete Math. 6 (1993), no. 1, 124–138. MR 1201995, 10.1137/0406010
  • 11. Henri Cohen, Sur la distribution asymptotique des groupes de classes, C. R. Acad. Sci. Paris Sér. I Math. 296 (1983), no. 5, 245–247 (French, with English summary). MR 693784
  • 12. H. HASSE, Über die Kongruenzzetafunktionen, Sitzungsb. d. Preuß . Akad. d. Wiss. H17, (1934), 250-263.
  • 13. H. HASSE & H. DAVENPORT, Die Nullstellen der Kongruenzzetafunktionen in gewissen zyklischen Fällen, Journal f. d. reine u. angew. Math. , 172 (1934), 151-182.
  • 14. F. HEIGL & J. FEUERPFEIL, Stochastik, BSV (1974).
  • 15. A.E. INGHAM, The Distribution of Prime Numbers, Cambridge Univ. Press, Cambridge, (1932).
  • 16. R. LOVORN [RENEE LOVORN BENDER], Rigorous, Subexponential Algorithms for Discrete Logarithms Over Finite Fields, PhD Thesis, University of Georgia (1992).
  • 17. R. LOVORN [RENEE LOVORN BENDER] & C. POMERANCE, Rigorous discrete logarithm computations in finite fields via smooth polynomials, Computational Perspectives on Number Theory (Chicago, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 221-232. CMP 98:05
  • 18. Kevin S. McCurley, Cryptographic key distribution and computation in class groups, Number theory and applications (Banff, AB, 1988) NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 265, Kluwer Acad. Publ., Dordrecht, 1989, pp. 459–479. MR 1123090
  • 19. A. MÜLLER, Lineare Algebra über $ \mathbf{Z}$, Diploma Thesis, Universität des Saarlandes, Saarbrücken, (1994).
  • 20. H. REICHARDT, Der Primdivisorsatz für algebraische Funktionenkörper über einem endlichen Konstantenkörper, Mathematische Zeitschrift 40 (1936), 713-719.
  • 21. 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, 10.1007/BF00125081
  • 22. F.K. SCHMIDT, Analytische Zahlentheorie in Körpern der Charakteristik p, Mathematische Zeitschrift 33 (1931), 1-32.
  • 23. R.J. SCHOOF, Quadratic fields and factorization, Computational Methods in Number Theory (H.W. Lenstra and R. Tijdemans, eds.,), Math. Centrum Tracts 155, Part II, Amsterdam (1983), 235-286. MR 85g:11118
  • 24. 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
  • 25. K. SOUNDARARAJAN, Smooth Polynomials: Analogies and Asymptotics, To appear in J. London Math. Society.
  • 26. A. STEIN, Baby Step-Giant Step-Verfahren in reell-quadratischen Kongruenzfunktionenkörpern mit Charakteristik ungleich 2, Diploma Thesis, Universität des Saarlandes, Saarbrücken, (1992).
  • 27. A. STEIN, Algorithmen in reell-quadratischen Kongruenzfunktionenkörpern, PhD Thesis, Universität des Saarlandes, Saarbrücken, (1996).
  • 28. A. STEIN & H.C. WILLIAMS, Some Methods for Evaluating the Regulator of a Real Quadratic Function Field, to appear in Experimental Mathematics.
  • 29. Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
  • 30. André Weil, Basic number theory, 3rd ed., Springer-Verlag, New York-Berlin, 1974. Die Grundlehren der Mathematischen Wissenschaften, Band 144. MR 0427267
  • 31. André Weil, Sur les courbes algébriques et les variétés qui s’en déduisent, Actualités Sci. Ind., no. 1041 = Publ. Inst. Math. Univ. Strasbourg 7 (1945), Hermann et Cie., Paris, 1948 (French). MR 0027151
  • 32. 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

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11Y16, 11R29, 11T71, 11R58, 68Q25, 94A60

Retrieve articles in all journals with MSC (1991): 11Y16, 11R29, 11T71, 11R58, 68Q25, 94A60

Additional Information

Volker Müller
Affiliation: Technische Universität Darmstadt, Fachbereich Informatik, Alexanderstr. 10, 64283 Darmstadt, Germany

Andreas Stein
Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1

Keywords: Discrete logarithm, class group, subexponential algorithm, real quadratic congruence function field
Received by editor(s): March 25, 1996
Received by editor(s) in revised form: September 10, 1997
Additional Notes: This research was supported by the Deutsche Forschungsgemeinschaft.
Article copyright: © Copyright 1999 American Mathematical Society