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
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
- Received by editor(s): January 30, 2000
- Received by editor(s) in revised form: October 3, 2000
- Published electronically: October 4, 2001
- © Copyright 2001 American Mathematical Society
- Journal: Math. Comp. 71 (2002), 1219-1230
- MSC (2000): Primary 11R58, 11Y16, 11R44, 14H40, 68Q25
- DOI: https://doi.org/10.1090/S0025-5718-01-01352-7
- MathSciNet review: 1898752