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 Free Access

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]**Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman,*The design and analysis of computer algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Second printing; Addison-Wesley Series in Computer Science and Information Processing. MR**0413592****[Coh96]**Henri Cohen,*A course in computational algebraic number theory*, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR**1228206****[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]**Andreas Enge and Pierrick Gaudry,*A general framework for subexponential discrete logarithm algorithms*, Acta Arith.**102**(2002), no. 1, 83–103. MR**1884958**, https://doi.org/10.4064/aa102-1-6**[Gau09]**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**, https://doi.org/10.1016/j.jsc.2008.08.005**[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**(2007), no. 257, 475–492. MR**2261032**, https://doi.org/10.1090/S0025-5718-06-01900-4**[Heß01]**F. Hess,*Computing Riemann-Roch spaces in algebraic function fields and related topics*, J. Symbolic Comput.**33**(2002), no. 4, 425–445. MR**1890579**, https://doi.org/10.1006/jsco.2001.0513**[Heß05]**F. Heß.

Computing relations in divisor class groups of algebraic curves over finite fields.

preprint, ca. 2005.**[LMD90]**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****[LW08]**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****[Nag07]**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****[Pil90]**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**, https://doi.org/10.1090/S0025-5718-1990-1035941-X**[Pil91]**J. Pila.

Counting points on curves over families in polynomial time.

Available on the arXiv under math.NT/0504570, 1991.**[Pom87]**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****[RS62]**J. Barkley Rosser and Lowell Schoenfeld,*Approximate formulas for some functions of prime numbers*, Illinois J. Math.**6**(1962), 64–94. MR**0137689****[Sch85]**René Schoof,*Elliptic curves over finite fields and the computation of square roots mod 𝑝*, Math. Comp.**44**(1985), no. 170, 483–494. MR**777280**, https://doi.org/10.1090/S0025-5718-1985-0777280-6**[Sem04]**I. Semaev.

Summation polynomials and the discrete logarithm problem on elliptic curves.

available under*http://eprint.iacr.org/2004/031*, 2004.**[Sti93]**Henning Stichtenoth,*Algebraic function fields and codes*, Universitext, Springer-Verlag, Berlin, 1993. MR**1251961**

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