On the discrete logarithm problem in class groups of curves
HTML articles powered by AMS MathViewer
- by Claus Diem PDF
- Math. Comp. 80 (2011), 443-475
Abstract:
We study the discrete logarithm problem in degree 0 class groups of curves over finite fields, with particular emphasis on curves of small genus. We prove that for every fixed $g \geq 2$, the discrete logarithm problem in degree 0 class groups of curves of genus $g$ can be solved in an expected time of $\tilde {\mathcal {O}}(q^{2 - \frac {2}{g}})$, where $\mathbb {F}_q$ is the ground field. This result generalizes a corresponding result for hyperelliptic curves given in imaginary quadratic representation with cyclic degree 0 class group, and just as this previous result, it is obtained via an index calculus algorithm with double large prime variation.
Generalizing this result, we prove that for fixed $g_0 \geq 2$ the discrete logarithm problem in class groups of all curves $\mathcal {C}/\mathbb {F}_q$ of genus $g \geq g_0$ can be solved in an expected time of $\tilde {\mathcal {O}}((q^{g})^{\frac {2}{g_0} (1 - \frac {1}{g_0})})$ and in an expected time of $\tilde {\mathcal {O}}(\# \mathrm {Cl}^0(\mathcal {C})^{\frac {2}{g_0} (1 - \frac {1}{g_0})})$.
As a complementary result we prove that for any fixed $n \in \mathbb {N}$ with $n \geq 2$ the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields $\mathbb {F}_{q^n}$, $q$ a prime power, can be solved in an expected time of $\tilde {\mathcal {O}}(q^{2 - \frac {2}{n}})$.
Furthermore, we give an algorithm for the efficient construction of a uniformly randomly distributed effective divisor of a specific degree, given the curve and its $L$-polynomial.
References
- Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing. MR 0413592
- Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
- C. Diem. On arithmetic and the discrete logarithm problem in class groups of curves, 2008. Habilitation thesis.
- C. Diem. On the discrete logarithm problem in elliptic curves. Accepted for publication at Compos. Math., 2010.
- Andreas Enge and Pierrick Gaudry, A general framework for subexponential discrete logarithm algorithms, Acta Arith. 102 (2002), no. 1, 83–103. MR 1884958, DOI 10.4064/aa102-1-6
- Pierrick Gaudry, Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem, J. Symbolic Comput. 44 (2009), no. 12, 1690–1702. MR 2553574, DOI 10.1016/j.jsc.2008.08.005
- P. Gaudry, E. Thomé, N. Thériault, and C. Diem, A double large prime variation for small genus hyperelliptic index calculus, Math. Comp. 76 (2007), no. 257, 475–492. MR 2261032, DOI 10.1090/S0025-5718-06-01900-4
- F. Hess, Computing Riemann-Roch spaces in algebraic function fields and related topics, J. Symbolic Comput. 33 (2002), no. 4, 425–445. MR 1890579, DOI 10.1006/jsco.2001.0513
- F. Heß. Computing relations in divisor class groups of algebraic curves over finite fields. preprint, ca. 2005.
- Gilles Lachaud and Mireille Martin-Deschamps, Nombre de points des jacobiennes sur un corps fini, Acta Arith. 56 (1990), no. 4, 329–340 (French). MR 1096346, DOI 10.4064/aa-56-4-329-340
- Alan G. B. Lauder and Daqing Wan, Counting points on varieties over finite fields of small characteristic, Algorithmic number theory: lattices, number fields, curves and cryptography, Math. Sci. Res. Inst. Publ., vol. 44, Cambridge Univ. Press, Cambridge, 2008, pp. 579–612. MR 2467558
- Koh-ichi Nagao, Index calculus attack for Jacobian of hyperelliptic curves of small genus using two large primes, Japan J. Indust. Appl. Math. 24 (2007), no. 3, 289–305. MR 2374992
- J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), no. 192, 745–763. MR 1035941, DOI 10.1090/S0025-5718-1990-1035941-X
- J. Pila. Counting points on curves over families in polynomial time. Available on the arXiv under math.NT/0504570, 1991.
- Carl Pomerance, Fast, rigorous factorization and discrete logarithm algorithms, Discrete algorithms and complexity (Kyoto, 1986) Perspect. Comput., vol. 15, Academic Press, Boston, MA, 1987, pp. 119–143. MR 910929
- J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
- René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
- I. Semaev. Summation polynomials and the discrete logarithm problem on elliptic curves. available under http://eprint.iacr.org/2004/031, 2004.
- Henning Stichtenoth, Algebraic function fields and codes, Universitext, Springer-Verlag, Berlin, 1993. MR 1251961
Additional Information
- Claus Diem
- Affiliation: University of Leipzig, Institute for Mathematics, Johannisgasse 26, 04103 Leipzig, Germany
- Email: diem@math.uni-leipzig.de
- Received by editor(s): November 26, 2008
- Received by editor(s) in revised form: March 25, 2009
- Published electronically: August 23, 2010
- © Copyright 2010 by the author
- Journal: Math. Comp. 80 (2011), 443-475
- MSC (2010): Primary 11Y16; Secondary 14G50, 68Q25, 94A60
- DOI: https://doi.org/10.1090/S0025-5718-2010-02281-1
- MathSciNet review: 2728990