HAL - INRIA :: [inria-00383941, version 2] An $L (1/3)$ Discrete Logarithm Algorithm for Low Degree Curves

inria-00383941, version 2

An $L (1/3)$ Discrete Logarithm Algorithm for Low Degree Curves

Andreas Enge () ¹, Pierrick Gaudry () ², Emmanuel Thomé () ²

Journal of Cryptology 24 (2011) 24-41

Résumé : We present an algorithm for solving the discrete logarithm problem in Jacobians of families of plane curves whose degrees in $X$ and $Y$ are low with respect to their genera. The finite base fields $\FF_q$ are arbitrary, but their sizes should not grow too fast compared to the genus. For such families, the group structure and discrete logarithms can be computed in subexponential time of $L_{q^g}(1/3, O(1))$. The runtime bounds rely on heuristics similar to the ones used in the number field sieve or the function field sieve.

1 : LFANT (INRIA Bordeaux - Sud-Ouest)
INRIA – Université de Bordeaux – CNRS : UMR5251
2 : CARAMEL (INRIA Nancy - Grand Est / LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine

inria-00383941, version 2
http://hal.inria.fr/inria-00383941
oai:hal.inria.fr:inria-00383941
Contributeur : Andreas Enge <>
Soumis le : Dimanche 20 Décembre 2009, 12:24:14
Dernière modification le : Jeudi 27 Janvier 2011, 17:00:25

Voir la fiche détaillée

Documents associés

PDF :

PS :

arXiv : 0905.2177

DOI : 10.1007/s00145-010-9057-y

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inria-00383941"><analytic>
<author><persName><forename>Andreas</forename><surname>Enge</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Bordeaux - Sud-Ouest</orgName>
<orgName type="team">LFANT</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">Université de Bordeaux</orgName>
<orgName type="institution">CNRS : UMR5251</orgName>
</affiliation>
</author>
<author><persName><forename>Pierrick</forename><surname>Gaudry</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Nancy - Grand Est / LORIA</orgName>
<orgName type="team">CARAMEL</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<author><persName><forename>Emmanuel</forename><surname>Thomé</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Nancy - Grand Est / LORIA</orgName>
<orgName type="team">CARAMEL</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine</orgName>
</affiliation>
</author>
<title type="main" level="a">An $L (1/3)$ Discrete Logarithm Algorithm for Low Degree Curves</title></analytic><monogr><title level="j" type="main">Journal of Cryptology</title><imprint><publisher>Springer-Verlag</publisher><biblScope type="publicationDate">2011-00-00</biblScope><biblScope type="vol">24</biblScope><biblScope type="pp">24-41</biblScope></imprint></monogr><idno type="doi">10.1007/s00145-010-9057-y</idno><idno type="HALid">http://hal.inria.fr/inria-00383941</idno><idno type="HALFile">http://hal.inria.fr/inria-00383941/PDF/L13.pdf</idno></biblStruct>
</listBibl>
</listBibl>