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 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 $ 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?)


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