Mathematics of Computation

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

Author(s): Volker Müller; Andreas Stein; Christoph Thiel.
Journal: Math. Comp. 68 (1999), 807-822.
MSC (1991): Primary 11Y16, 11R29; Secondary 11T71, 11R58, 68Q25, 94A60
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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.

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

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS