Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

   
 
 

 

On the discrete logarithm problem in class groups of curves


Author: Claus Diem
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
Published electronically: August 23, 2010
MathSciNet review: 2728990
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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}}(\char93 \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 [Enhancements On Off] (What's this?)

  • [AHU74] A. Aho, J. Hopcroft, and J. Ullman.
    The design and analysis of computer algorithms.
    Addison-Wesley, 1974. MR 0413592 (54:1706)
  • [Coh96] H. Cohen.
    A course in computational algebraic number theory.
    Springer-Verlag, 1996. MR 1228206 (94i:11105)
  • [Die08] C. Diem.
    On arithmetic and the discrete logarithm problem in class groups of curves, 2008.
    Habilitation thesis.
  • [Die10] C. Diem.
    On the discrete logarithm problem in elliptic curves.
    Accepted for publication at Compos. Math., 2010.
  • [EG02] A. Enge and P. Gaudry.
    A general framework for subexponential discrete logarithm algorithms.
    Acta. Arith., 102:83-103, 2002. MR 1884958 (2002k:11225)
  • [Gau09] P. Gaudry.
    Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem.
    J. Symbolic Computation, 44:1690-1702, 2009. MR 2553574
  • [GTTD07] P. Gaudry, E. Thomé, N. Thériault, and C. Diem.
    A double large prime variation for small genus hyperelliptic index calculus.
    Math. Comp., 76:475-492, 2007. MR 2261032 (2007j:11174)
  • [Heß01] F. Heß.
    Computing Riemann-Roch spaces in algebraic function fields and related topics.
    J. Symb. Comput., 11, 2001. MR 1890579 (2003j:14032)
  • [Heß05] F. Heß.
    Computing relations in divisor class groups of algebraic curves over finite fields.
    preprint, ca. 2005.
  • [LMD90] G. Lachaud and M. Martin-Deschamps.
    Nombre de points des jacobiennes sur un corps fini.
    Acta. Arith., 56:329-340, 1990. MR 1096346 (92d:11065)
  • [LW08] A. Lauder and D. Wan.
    Counting points on varieties over finite fields of small characteristic.
    In J. Buhler and P. Stevenhagen, editors, Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography. Cambridge University Press, 2008. MR 2467558 (2009j:14029)
  • [Nag07] K. Nagao.
    Index calculus attack for Jacobian of hyperelliptic curves of small genus using two large primes.
    Japan J. Indust. Appl. Math., 24, 2007. MR 2374992 (2008m:11243)
  • [Pil90] J. Pila.
    Frobenius maps of abelian varieties and fining roots of unity in finite fields.
    Math. Comp., 55:745-763, 1990. MR 1035941 (91a:11071)
  • [Pil91] J. Pila.
    Counting points on curves over families in polynomial time.
    Available on the arXiv under math.NT/0504570, 1991.
  • [Pom87] C. Pomerance.
    Fast, rigorous factorization and discrete logarithm algorithms.
    In D. Johnson, T. Nishizeki, A. Nozaki, and H. Wolf, editors, Discrete Algorithms and Complexity, Proceedings of the Japan US Joint Seminar, June 4-6, 1986, Kyoto, Japan, pages 119-143, 1987. MR 910929 (88m:11109)
  • [RS62] J. Rosser and L. Schoenfeld.
    Approximate formulas for some functions of prime numbers.
    Illinois J. Math., 6(64-94), 1962. MR 0137689 (25:1139)
  • [Sch85] R. Schoof.
    Elliptic curves over finite fields and the computation of square roots mod $ p$.
    Math. Comp., 44:483-494, 1985. MR 777280 (86e:11122)
  • [Sem04] I. Semaev.
    Summation polynomials and the discrete logarithm problem on elliptic curves.
    available under http://eprint.iacr.org/2004/031, 2004.
  • [Sti93] H. Stichtenoth.
    Algebraic Function Fields and Codes.
    Springer-Verlag, 1993. MR 1251961 (94k:14016)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11Y16, 14G50, 68Q25, 94A60

Retrieve articles in all journals with MSC (2010): 11Y16, 14G50, 68Q25, 94A60


Additional Information

Claus Diem
Affiliation: University of Leipzig, Institute for Mathematics, Johannisgasse 26, 04103 Leipzig, Germany
Email: diem@math.uni-leipzig.de

DOI: https://doi.org/10.1090/S0025-5718-2010-02281-1
Keywords: Discrete logarithm problem, curves, index calculus
Received by editor(s): November 26, 2008
Received by editor(s) in revised form: March 25, 2009
Published electronically: August 23, 2010
Article copyright: © Copyright 2010 by the author

American Mathematical Society