Smooth ideals in hyperelliptic function fields

Enge, Andreas; Stein, Andreas

doi:10.1090/S0025-5718-01-01352-7

Smooth ideals in hyperelliptic function fields
HTML articles powered by AMS MathViewer

by Andreas Enge and Andreas Stein PDF

Math. Comp. 71 (2002), 1219-1230 Request permission

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

Leonard M. Adleman and Jonathan DeMarrais, A subexponential algorithm for discrete logarithms over all finite fields, Math. Comp. 61 (1993), no. 203, 1–15. MR 1225541, DOI 10.1090/S0025-5718-1993-1225541-3
Hermann Kober, Transformationen von algebraischem Typ, Ann. of Math. (2) 40 (1939), 549–559 (German). MR 96, DOI 10.2307/1968939
Leonard M. Adleman and Ming-Deh Huang (eds.), Algorithmic number theory, Lecture Notes in Computer Science, vol. 877, Springer-Verlag, Berlin, 1994. MR 1322704, DOI 10.1007/3-540-58691-1
E. Artin. Quadratische Körper im Gebiete der höheren Kongruenzen I, II. Mathematische Zeitschrift, 19:153–206, 1924.
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.
Renet Lovorn Bender and Carl Pomerance, Rigorous discrete logarithm computations in finite fields via smooth polynomials, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 221–232. MR 1486839, DOI 10.1090/amsip/007/11
D. A. Buell and J. T. Teitelbaum (eds.), Computational perspectives on number theory, AMS/IP Studies in Advanced Mathematics, vol. 7, American Mathematical Society, Providence, RI; International Press, Cambridge, MA, 1998. MR 1486828, DOI 10.1090/amsip/007
J. P. Buhler (ed.), Algorithmic number theory, Lecture Notes in Computer Science, vol. 1423, Springer-Verlag, Berlin, 1998. MR 1726058, DOI 10.1007/BFb0054849
Mireille Car, Théorèmes de densité dans $\textbf {F}_q[X]$, Acta Arith. 48 (1987), no. 2, 145–165 (French). MR 895437, DOI 10.4064/aa-48-2-145-165
Whitfield Diffie and Martin E. Hellman, New directions in cryptography, IEEE Trans. Inform. Theory IT-22 (1976), no. 6, 644–654. MR 437208, DOI 10.1109/tit.1976.1055638
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.
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.
Florian Heß. Zur Divisorenklassengruppenberechnung in globalen Funktionenkörpern. PhD thesis, Technische Universität Berlin, 1999.
John Knopfmacher, Abstract analytic number theory, North-Holland Mathematical Library, Vol. 12, North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, 1975. MR 0419383
Neal Koblitz, Elliptic curve cryptosystems, Math. Comp. 48 (1987), no. 177, 203–209. MR 866109, DOI 10.1090/S0025-5718-1987-0866109-5
Neal Koblitz, Hyperelliptic cryptosystems, J. Cryptology 1 (1989), no. 3, 139–150. MR 1007215, DOI 10.1007/BF02252872
E. Manstavichyus, Remarks on elements of semigroups that are free of large prime factors, Liet. Mat. Rink. 32 (1992), no. 4, 512–525 (Russian, with Lithuanian summary); English transl., Lithuanian Math. J. 32 (1992), no. 4, 400–409 (1993). MR 1246042, DOI 10.1007/BF00970673
E. Manstavičius, Semigroup elements free of large prime factors, New trends in probability and statistics, Vol. 2 (Palanga, 1991) VSP, Utrecht, 1992, pp. 135–153. MR 1198497
Victor S. Miller, Use of elliptic curves in cryptography, Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif., 1985) Lecture Notes in Comput. Sci., vol. 218, Springer, Berlin, 1986, pp. 417–426. MR 851432, DOI 10.1007/3-540-39799-X_{3}1
Volker Müller, Andreas Stein, and Christoph Thiel, Computing discrete logarithms in real quadratic congruence function fields of large genus, Math. Comp. 68 (1999), no. 226, 807–822. MR 1620235, DOI 10.1090/S0025-5718-99-01040-6
Daniel Panario, Xavier Gourdon, and Philippe Flajolet, An analytic approach to smooth polynomials over finite fields, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 226–236. MR 1726074, DOI 10.1007/BFb0054865
Sachar Paulus and Hans-Georg Rück, Real and imaginary quadratic representations of hyperelliptic function fields, Math. Comp. 68 (1999), no. 227, 1233–1241. MR 1627817, DOI 10.1090/S0025-5718-99-01066-2
R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120–126. MR 700103, DOI 10.1145/359340.359342
Martin Seysen, A probabilistic factorization algorithm with quadratic forms of negative discriminant, Math. Comp. 48 (1987), no. 178, 757–780. MR 878705, DOI 10.1090/S0025-5718-1987-0878705-X
F. Schweiger and E. Manstavičius (eds.), New trends in probability and statistics. Vol. 2, VSP, Utrecht; TEV Ltd., Vilnius, 1992. Analytic and probabilistic methods in number theory. MR 1198480
K. Soundararajan. Smooth polynomials: Analogies and asymptotics. Preprint, July 1998.
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
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).
Andreas Stein, Equivalences between elliptic curves and real quadratic congruence function fields, J. Théor. Nombres Bordeaux 9 (1997), no. 1, 75–95 (English, with English and French summaries). MR 1469663
Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
Andreas Stein and Hugh C. Williams, Some methods for evaluating the regulator of a real quadratic function field, Experiment. Math. 8 (1999), no. 2, 119–133. MR 1700574
Robert J. Zuccherato, The equivalence between elliptic curve and quadratic function field discrete logarithms in characteristic 2, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 621–638. MR 1726106, DOI 10.1007/BFb0054897