Abstract
There are well known subexponential algorithms for finding discrete logarithms over finite fields. However, the methods which underlie these algorithms do not appear to be easily adaptable for finding discrete logarithms in the groups associated with elliptic curves and the Jacobians of hyperelliptic curves. This has led to the development of cryptographic systems based on the discrete logarithm problem for such groups [12, 7, 8]. In this paper a Subexponential algorithm is presented for finding discrete logarithms in the group of rational points on the Jacobians of large genus hyperelliptic curves over finite fields. We give a heuristic argument that under certain assumptions, there exists a c ε ℜ>0 such that for all sufficiently large g ε Z >0, for all odd primes p with log p ≤ (2g + 1).98, the algorithm computes discrete logarithms in the group of rational points on the Jacobian of a genus g hyperelliptic curve over GF(p) within expected time: L p2g+1[1/2, c] where c ≤ 2.181.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Berlekamp, E.R., Factoring Polynomials over Large Finite Fields, Math. Comp. 24 (1970),713–715.
Cantor, D., Computing in the Jacobian of a Hyperelliptic Curve, Math. Comp., Num. 177, 1987, pp. 95–101
Hartshorne, R., Algebraic Geometry, Springer-Verlag, New York, 1977.
Iliopoulos, C., Worst case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith Normal forms of an integer matrix, SIAM J. Comput., 18, 1989, pp. 658–669
Jacobson, N., Basic Algebra I, W. H. Freeman and company, 1974
Kannan, R. and Bachem A., Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix, SIAM J. Comput., 8, 1979, pp. 499–507
Koblitz, N., Elliptic curve cryptosystems, Math. Comp., 1987.
Koblitz, N., Hyperelliptic Cryptosystems, J. Cryptography 1, 1989, pp. 139–150.
Lenstra H. W., Algorithms in Algebraic Number Theory, Preliminary version, May 20 1991.
Lovorn R., Rigorous, subexponenial algorithms for discrete logarithms over finite fields, PhD Thesis, University of Georgia, May 1992
Mumford, D., Tata Lectures on Theta II, Birkhäuser, Boston, 1984.
Miller, V., The use of elliptic curves in cryptography. Advances in Cryptography, Ed. H.C. Williams, Springer-Verlag, 1986, 417–426.
Rabin, M. O., Probabilistic Algorithms in Finite Fields, Siam J. Comput. 9 (1980) 273–280
Zantema, H., Class Numbers and Units, Computational Methods in Number Theory, Part II, 1987, 213–234
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Adleman, L.M., DeMarrais, J., Huang, MD. (1994). A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields. In: Adleman, L.M., Huang, MD. (eds) Algorithmic Number Theory. ANTS 1994. Lecture Notes in Computer Science, vol 877. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58691-1_39
Download citation
DOI: https://doi.org/10.1007/3-540-58691-1_39
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58691-3
Online ISBN: 978-3-540-49044-9
eBook Packages: Springer Book Archive