Remote Access Mathematics of Computation
Green Open Access

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

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. E. BACH, Explicit Bounds for Primality Testing and Related Problems, Math. Comp., Vol 55, Number 191 (1990), 355-380. MR 91m:11096
  • 4. J. 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) 28-41. MR 92g:11125
  • 5. J. BUCHMANN, C. THIEL & H.C. WILLIAMS, Short representation of quadratic integers, Computational Algebra and Number Theory (Sydney, 1992), Math. Appl., vol. 325, Reidel, Dordrecht, 1995, pp. 159-185.MR 96c:11144
  • 6. H. COHEN, A course in computational algebraic number theory, Springer Verlag (1993). MR 94i:11105
  • 7. M. DEURING, Lectures on the Theory of Algebraic Functions of One Variable, Lect. Notes in Math. 314, Berlin (1973). MR 49:8970
  • 8. P. D. DOMICH & R. KANNAN & L. E. TROTTER JR., Hermite normal form computation using modular determinant arithmetic, Math. of Operations Research 12, No. 1, February (1987), 50-59. MR 88e:65047
  • 9. M. EICHLER, Introduction to the Theory of Algebraic Numbers and Functions, Academic Press, New York (1966). MR 35:160
  • 10. D. GORDON, Discrete Logarithms in $\mathrm{GF}(p)$ using the Number Field Sieve, SIAM J. Discrete Math. 6 (1993), 124-138. MR 94d:11104
  • 11. H. HASSE, Number Theory, Springer, New York, 1980. MR 84c:12001
  • 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. K.S. MCCURLEY, Cryptographic key distribution and computation in class groups, Proceedings of NATO ASI Number Theory and Applications, Kluwer Academic Publishers (1989), 459-479. MR 92e:11149
  • 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 & H.C. WILLIAMS, Key-exchange in real quadratic congruence function fields, Designs, Codes and Cryptography, Vol. 7, Number 1/2 (1996), 153-174. MR 97d:94009
  • 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. D. SHANKS, The infrastructure of a real quadratic field and its applications, Proc. 1972 Number Theory Conference, Boulder, (1972), 217-224. MR 52:10672
  • 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. H. STICHTENOTH, Algebraic Function Fields and Codes, Springer Verlag, Berlin (1993). MR 94k:14016
  • 30. A. WEIL, Basic Number Theory, Third Edition, Springer Verlag (1974). MR 55:302
  • 31. A. WEIL, Sur les Courbes Algébriques et les Variétés qui s'en Déduisent, Hermann, Paris, (1948). MR 10:262c
  • 32. 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, Sond. , XII, 2, (1991), 261-282. MR 93e:11141

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

American Mathematical Society