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 , the discrete logarithm problem in degree 0 class groups of curves of genus can be solved in an expected time of , where 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 the discrete logarithm problem in class groups of all curves of genus can be solved in an expected time of and in an expected time of .

As a complementary result we prove that for any fixed with the discrete logarithm problem in the groups of rational points of elliptic curves over finite fields , a prime power, can be solved in an expected time of .

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 -polynomial.

**[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 .*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)**

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