An L (1/3 + ε ) Algorithm for the Discrete Logarithm Problem for Low Degree Curves
Identifieur interne : 004D11 ( Main/Exploration ); précédent : 004D10; suivant : 004D12An L (1/3 + ε ) Algorithm for the Discrete Logarithm Problem for Low Degree Curves
Auteurs : Andreas Enge [France] ; Pierrick Gaudry [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: The discrete logarithm problem in Jacobians of curves of high genus g over finite fields $\mathbb {F}_q$ is known to be computable with subexponential complexity $L_{q^g}(1/2, O(1))$ . We present an algorithm for a family of plane curves whose degrees in X and Y are low with respect to the curve genus, and suitably unbalanced. The finite base fields are arbitrary, but their sizes should not grow too fast compared to the genus. For this family, the group structure can be computed in subexponential time of $L_{q^g}(1/3, O(1))$ , and a discrete logarithm computation takes subexponential time of $L_{q^g}(1/3+ \varepsilon, o(1))$ for any positive ε. These runtime bounds rely on heuristics similar to the ones used in the number field sieve or the function field sieve algorithms.
Url:
DOI: 10.1007/978-3-540-72540-4_22
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 000F55
- to stream Istex, to step Curation: 000F41
- to stream Istex, to step Checkpoint: 001096
- to stream Main, to step Merge: 004E45
- to stream Main, to step Curation: 004D11
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">An L (1/3 + ε ) Algorithm for the Discrete Logarithm Problem for Low Degree Curves</title><author><name sortKey="Enge, Andreas" sort="Enge, Andreas" uniqKey="Enge A" first="Andreas" last="Enge">Andreas Enge</name></author><author><name sortKey="Gaudry, Pierrick" sort="Gaudry, Pierrick" uniqKey="Gaudry P" first="Pierrick" last="Gaudry">Pierrick Gaudry</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:421E119C74EB9AE3357CEC6D6152E462DD4BBE76</idno><date when="2007" year="2007">2007</date><idno type="doi">10.1007/978-3-540-72540-4_22</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-WH9C6QJG-3/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">000F55</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000F55</idno><idno type="wicri:Area/Istex/Curation">000F41</idno><idno type="wicri:Area/Istex/Checkpoint">001096</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001096</idno><idno type="wicri:doubleKey">0302-9743:2007:Enge A:an:l:algorithm</idno><idno type="wicri:Area/Main/Merge">004E45</idno><idno type="wicri:Area/Main/Curation">004D11</idno><idno type="wicri:Area/Main/Exploration">004D11</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">An <hi rend="italic">L</hi> (1/3 + <hi rend="italic">ε</hi>) Algorithm for the Discrete Logarithm Problem for Low Degree Curves</title><author><name sortKey="Enge, Andreas" sort="Enge, Andreas" uniqKey="Enge A" first="Andreas" last="Enge">Andreas Enge</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>INRIA Futurs & Laboratoire d’Informatique (CNRS/UMR 7161), École polytechnique, 91128, Palaiseau Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Île-de-France</region><settlement type="city">Palaiseau</settlement></placeName></affiliation></author><author><name sortKey="Gaudry, Pierrick" sort="Gaudry, Pierrick" uniqKey="Gaudry P" first="Pierrick" last="Gaudry">Pierrick Gaudry</name><affiliation wicri:level="3"><country xml:lang="fr">France</country><wicri:regionArea>LORIA (CNRS/UMR 7503), Campus Scientifique, BP 239, 54506, Vandœuvre-lés-Nancy Cedex</wicri:regionArea><placeName><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region><settlement type="city">Vandœuvre-lès-Nancy</settlement></placeName></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The discrete logarithm problem in Jacobians of curves of high genus g over finite fields $\mathbb {F}_q$ is known to be computable with subexponential complexity $L_{q^g}(1/2, O(1))$ . We present an algorithm for a family of plane curves whose degrees in X and Y are low with respect to the curve genus, and suitably unbalanced. The finite base fields are arbitrary, but their sizes should not grow too fast compared to the genus. For this family, the group structure can be computed in subexponential time of $L_{q^g}(1/3, O(1))$ , and a discrete logarithm computation takes subexponential time of $L_{q^g}(1/3+ \varepsilon, o(1))$ for any positive ε. These runtime bounds rely on heuristics similar to the ones used in the number field sieve or the function field sieve algorithms.</div></front></TEI><affiliations><list><country><li>France</li></country><region><li>Grand Est</li><li>Lorraine (région)</li><li>Île-de-France</li></region><settlement><li>Palaiseau</li><li>Vandœuvre-lès-Nancy</li></settlement></list><tree><country name="France"><region name="Île-de-France"><name sortKey="Enge, Andreas" sort="Enge, Andreas" uniqKey="Enge A" first="Andreas" last="Enge">Andreas Enge</name></region><name sortKey="Gaudry, Pierrick" sort="Gaudry, Pierrick" uniqKey="Gaudry P" first="Pierrick" last="Gaudry">Pierrick Gaudry</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004D11 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 004D11 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:421E119C74EB9AE3357CEC6D6152E462DD4BBE76
|texte= An L (1/3 + ε ) Algorithm for the Discrete Logarithm Problem for Low Degree Curves
}}
| This area was generated with Dilib version V0.6.33. |  |