Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Computing discrete logarithms in real quadratic congruence function fields of large genus
HTML articles powered by AMS MathViewer

by Volker Müller, Andreas Stein and Christoph Thiel PDF
Math. Comp. 68 (1999), 807-822 Request permission

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
  • C.S. Abel, Ein Algorithmus zur Berechnung der Klassenzahl und des Regulators reellquadratischer Ordnungen, PhD Thesis, Universität des Saarlandes, Saarbrücken, (1994).
  • E. Artin, Quadratische Körper im Gebiete der höheren Kongruenzen I, II, Math. Zeitschr. 19 (1924), 153-206.
  • Eric Bach, Explicit bounds for primality testing and related problems, Math. Comp. 55 (1990), no. 191, 355–380. MR 1023756, DOI 10.1090/S0025-5718-1990-1023756-8
  • 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
  • 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
  • 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
  • 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
  • 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, DOI 10.1287/moor.12.1.50
  • Martin Eichler, Introduction to the theory of algebraic numbers and functions, Pure and Applied Mathematics, Vol. 23, Academic Press, New York-London, 1966. Translated from the German by George Striker. MR 0209258
  • Daniel M. Gordon, Discrete logarithms in $\textrm {GF}(p)$ using the number field sieve, SIAM J. Discrete Math. 6 (1993), no. 1, 124–138. MR 1201995, DOI 10.1137/0406010
  • 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
  • H. Hasse, Über die Kongruenzzetafunktionen, Sitzungsb. d. Preuß. Akad. d. Wiss. H17, (1934), 250-263.
  • H. Hasse & H. Davenport, Die Nullstellen der Kongruenzzetafunktionen in gewissen zyklischen Fällen, Journal f. d. reine u. angew. Math. , 172 (1934), 151-182.
  • F. Heigl & J. Feuerpfeil, Stochastik, BSV (1974).
  • A.E. Ingham, The Distribution of Prime Numbers, Cambridge Univ. Press, Cambridge, (1932).
  • R. Lovorn [Renee Lovorn Bender], Rigorous, Subexponential Algorithms for Discrete Logarithms Over Finite Fields, PhD Thesis, University of Georgia (1992).
  • 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.
  • 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
  • A. Müller, Lineare Algebra über $\mathbf {Z}$, Diploma Thesis, Universität des Saarlandes, Saarbrücken, (1994).
  • H. Reichardt, Der Primdivisorsatz für algebraische Funktionenkörper über einem endlichen Konstantenkörper, Mathematische Zeitschrift 40 (1936), 713-719.
  • 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
  • F.K. Schmidt, Analytische Zahlentheorie in Körpern der Charakteristik p, Mathematische Zeitschrift 33 (1931), 1-32.
  • Alfred Rosenblatt, Sur les points singuliers des équations différentielles, C. R. Acad. Sci. Paris 209 (1939), 10–11 (French). MR 85
  • 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
  • K. Soundararajan, Smooth Polynomials: Analogies and Asymptotics, To appear in J. London Math. Society.
  • 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).
  • A. Stein, Algorithmen in reell-quadratischen Kongruenzfunktionenkörpern, PhD Thesis, Universität des Saarlandes, Saarbrücken, (1996).
  • A. Stein & H.C. Williams, Some Methods for Evaluating the Regulator of a Real Quadratic Function Field, to appear in Experimental Mathematics.
  • Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
  • André Weil, Basic number theory, 3rd ed., Die Grundlehren der mathematischen Wissenschaften, Band 144, Springer-Verlag, New York-Berlin, 1974. MR 0427267
  • Morgan Ward, Ring homomorphisms which are also lattice homomorphisms, Amer. J. Math. 61 (1939), 783–787. MR 10, DOI 10.2307/2371336
  • 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
Additional Information
  • Volker Müller
  • Affiliation: Technische Universität Darmstadt, Fachbereich Informatik, Alexanderstr. 10, 64283 Darmstadt, Germany
  • Email: vmueller@cdc.informatik.tu-darmstadt.de
  • Andreas Stein
  • Affiliation: Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, N2L 3G1
  • Email: astein@cacr.math.uwaterloo.ca
  • 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.
  • © Copyright 1999 American Mathematical Society
  • Journal: Math. Comp. 68 (1999), 807-822
  • MSC (1991): Primary 11Y16, 11R29; Secondary 11T71, 11R58, 68Q25, 94A60
  • DOI: https://doi.org/10.1090/S0025-5718-99-01040-6
  • MathSciNet review: 1620235