Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
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
     

Smooth ideals in hyperelliptic function fields

Author(s): Andreas Enge; Andreas Stein.
Journal: Math. Comp. 71 (2002), 1219-1230.
MSC (2000): Primary 11R58, 11Y16, 11R44, 14H40, 68Q25
Posted: October 4, 2001
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract | References | Similar articles | Additional information

Abstract: Recently, several algorithms have been suggested for solving the discrete logarithm problem in the Jacobians of high-genus hyperelliptic curves over finite fields. Some of them have a provable subexponential running time and are using the fact that smooth reduced ideals are sufficiently dense. We explicitly show how these density results can be derived. All proofs are purely combinatorial and do not exploit analytic properties of generating functions.

References:

[AD93]
Leonard M. Adleman and Jonathan DeMarrais.
A subexponential algorithm for discrete logarithms over all finite fields.
Mathematics of Computation, 61(203):1-15, 1993. MR 94e:11140

[ADH94]
Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh Huang.
A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields.
In [AH94], pages 28-40, 1994. MR 96b:111078

[AH94]
Leonard M. Adleman and Ming-Deh Huang, editors.
Algorithmic Number Theory, volume 877 of Lecture Notes in Computer Science, Berlin, 1994. Springer-Verlag. MR 95j:11119

[Art24]
E. Artin.
Quadratische Körper im Gebiete der höheren Kongruenzen I, II.
Mathematische Zeitschrift, 19:153-206, 1924.

[Bau98]
Mark Bauer.
A subexponential algorithm for solving the discrete logarithm problem in the Jacobian of high genus hyperelliptic curves over arbitrary finite fields.
Preprint, 1998.

[BP98]
Renet Lovorn Bender and Carl Pomerance.
Rigorous discrete logarithm computations in finite fields via smooth polynomials.
In [BT98], pages 221-232, 1998. MR 99c:11156

[BT98]
D. A. Buell and J. T. Teitelbaum, editors.
Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A.O.L. Atkin, volume 7 of Studies in Advanced Mathematics. American Mathematical Society, 1998. MR 98g:11001

[Buh98]
J. P. Buhler, editor.
Algorithmic Number Theory -- ANTS-III, volume 1423 of Lecture Notes in Computer Science, Berlin, 1998. Springer-Verlag. MR 2000g:11002

[Car87]
Mireille Car.
Théorèmes de densité dans $\mathbb {F}_q [x]$.
Acta Arithmetica, 68:145-165, 1987. MR 88g:11090

[DH76]
Whitfield Diffie and Martin E. Hellman.
New directions in cryptography.
IEEE Transactions on Information Theory, 22(6):644-655, November 1976. MR 55:10141

[EG00]
Andreas Enge and Pierrick Gaudry.
A general framework for subexponential discrete logarithm algorithms.
Research Report LIX/RR/00/04, LIX, June 2000.
Available at http://www.math.uni-augsburg.de/~enge/vorabdrucke/subexp.ps.gz.

[Eng99]
Andreas Enge.
Computing discrete logarithms in high-genus hyperelliptic Jacobians in provably subexponential time.
Combinatorics and Optimization Research Report CORR 99-04, University of Waterloo, February 1999.
Available at http://cacr.math.uwaterloo.ca/techreports/1999/corr99-04.ps; to appear in Mathematics of Computation.

[Heß99]
Florian Heß.
Zur Divisorenklassengruppenberechnung in globalen Funktionenkörpern.
PhD thesis, Technische Universität Berlin, 1999.

[Kno75]
John Knopfmacher.
Abstract Analytic Number Theory, volume 12 of North-Holland Mathematical Library.
North-Holland Publishing Company, Amsterdam, 1975. MR 54:7404

[Kob87]
Neal Koblitz.
Elliptic curve cryptosystems.
Mathemathics of Computation, 48:203-209, 1987. MR 88b:94017

[Kob89]
Neal Koblitz.
Hyperelliptic cryptosystems.
Journal of Cryptology, 1:139-150, 1989. MR 90k:11165

[Man92a]
E. Manstavicius.
Remarks on the semigroup elements free of large prime factors.
Lithuanian Mathematical Journal, 32(4):400-409, 1992. MR 94j:11093

[Man92b]
E. Manstavicius.
Semigroup elements free of large prime factors.
In [SM92], pages 135-153, 1992. MR 93m:11091

[Mil86]
V. Miller.
Use of elliptic curves in cryptography.
In CRYPTO'85, volume 218 of Lecture Notes in Computer Science, pages 417-426. Springer, 1986. MR 88b:68040

[MST99]
V. Müller, A. Stein, and C. Thiel.
Computing discrete logarithms in real quadratic congruence function fields of large genus.
Mathematics of Computation, 68(226):807-822, 1999. MR 99i:11119

[PGF98]
D. Panario, X. Gourdon, and P. Flajolet.
An analytic approach to smooth polynomials over finite fields.
In [Buh98], pages 226-236, 1998. MR 2001e:11119

[PR99]
S. Paulus and H.-G. Rück.
Real and imaginary quadratic representations of hyperelliptic function fields.
Mathematics of Computation, 68:1233-1241, 1999. MR 99i:11107

[RSA78]
R. L. Rivest, A. Shamir, and L. Adleman.
A method for obtaining digital signatures and public-key cryptosystems.
Communications of the ACM, 21(2):120-126, February 1978. MR 83m:94003

[Sey87]
M. Seysen.
A probabilistic factorization algorithm with quadratic forms of negative discriminant.
Mathematics of Computation, 48(178):757-780, 1987. MR 88d:11129

[SM92]
F. Schweiger and E. Manstavicius, editors.
New Trends in Probab. and Statist., 1992. MR 93g:11005

[Sou98]
K. Soundararajan.
Smooth polynomials: Analogies and asymptotics.
Preprint, July 1998.

[SSW96]
R. Scheidler, A. Stein, and H. C. Williams.
Key-exchange in real quadratic congruence function fields.
Designs, Codes and Cryptography, 7:153-174, 1996. MR 97d:94009

[ST99]
A. Stein and E. Teske.
Explicit bounds and heuristics on class numbers in hyperelliptic function fields.
Technical Report CORR 99-26, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, 1999; Math. Comp., posted on October 4, 2001, PII S0025-5718(01)01385-0 (to appear in print).

[Ste97]
A. Stein.
Equivalences between elliptic curves and real quadratic congruence function fields.
Journal de Theorie des Nombres de Bordeaux, 9:75-95, 1997. MR 98d:11144

[Sti93]
H. Stichtenoth.
Algebraic Function Fields and Codes.
Springer, Berlin, 1993. MR 94k:14016

[SW99]
A. Stein and H. C. Williams.
Some methods for evaluating the regulator of a real quadratic function field.
Experimental Mathematics, 8(2):119-133, 1999. MR 2000f:11152

[Zuc98]
R. Zuccherato.
The equivalence between elliptic curve and quadratic function field discrete logarithms in characteristic 2.
In Algorithmic Number Theory Seminar ANTS-III, volume 1423 of Lecture Notes in Computer Science, pages 621-638. Springer, 1998. MR 2000j:14043

Similar Articles:

Retrieve articles in Mathematics of Computation with MSC (2000): 11R58, 11Y16, 11R44, 14H40, 68Q25

Retrieve articles in all Journals with MSC (2000): 11R58, 11Y16, 11R44, 14H40, 68Q25

Additional Information:

Andreas Enge
Affiliation: Lehrstuhl für Diskrete Mathematik, Optimierung und Operations Research, Universität Augsburg, 86135 Augsburg, Germany
Email: enge@math.uni-augsburg.de

Andreas Stein
Affiliation: University of Illinois at Urbana-Champaign, Department of Mathematics, 1409 West Green Street, Urbana, Illinois 61801
Email: andreas@math.uiuc.edu

DOI: 10.1090/S0025-5718-01-01352-7
PII: S 0025-5718(01)01352-7
Keywords: Distribution of prime ideals, smooth ideal, hyperelliptic function field, subexponential algorithm
Received by editor(s): January 30, 2000
Received by editor(s) in revised form: October 3, 2000
Posted: October 4, 2001
Copyright of article: Copyright 2001, American Mathematical Society

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google