A double large prime variation for small genus hyperelliptic index calculus
Identifieur interne : 006090 ( Main/Exploration ); précédent : 006089; suivant : 006091A double large prime variation for small genus hyperelliptic index calculus
Auteurs : Pierrick Gaudry ; Emmanuel Thomé ; Nicolas Thériault ; Claus DiemSource :
- Mathematics of Computation ; 2005.
Abstract
In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard's Rho method even for rather small field sizes.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Crin, to step Corpus: 004517
- to stream Crin, to step Curation: 004517
- to stream Crin, to step Checkpoint: 000538
- to stream Main, to step Merge: 006313
- to stream Main, to step Curation: 006090
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" wicri:score="112">A double large prime variation for small genus hyperelliptic index calculus</title>
</titleStmt>
<publicationStmt><idno type="RBID">CRIN:gaudry05b</idno>
<date when="2005" year="2005">2005</date>
<idno type="wicri:Area/Crin/Corpus">004517</idno>
<idno type="wicri:Area/Crin/Curation">004517</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Curation">004517</idno>
<idno type="wicri:Area/Crin/Checkpoint">000538</idno>
<idno type="wicri:explorRef" wicri:stream="Crin" wicri:step="Checkpoint">000538</idno>
<idno type="wicri:Area/Main/Merge">006313</idno>
<idno type="wicri:Area/Main/Curation">006090</idno>
<idno type="wicri:Area/Main/Exploration">006090</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">A double large prime variation for small genus hyperelliptic index calculus</title>
<author><name sortKey="Gaudry, Pierrick" sort="Gaudry, Pierrick" uniqKey="Gaudry P" first="Pierrick" last="Gaudry">Pierrick Gaudry</name>
</author>
<author><name sortKey="Thome, Emmanuel" sort="Thome, Emmanuel" uniqKey="Thome E" first="Emmanuel" last="Thomé">Emmanuel Thomé</name>
</author>
<author><name sortKey="Theriault, Nicolas" sort="Theriault, Nicolas" uniqKey="Theriault N" first="Nicolas" last="Thériault">Nicolas Thériault</name>
</author>
<author><name sortKey="Diem, Claus" sort="Diem, Claus" uniqKey="Diem C" first="Claus" last="Diem">Claus Diem</name>
</author>
</analytic>
<series><title level="j">Mathematics of Computation</title>
<imprint><date when="2005" type="published">2005</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en" wicri:score="1612">In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a considerably simplified variant, which can be analyzed easily. The resulting complexity improves on the fastest known algorithms. Computer experiments show that for hyperelliptic curves of genus three, our first algorithm surpasses Pollard's Rho method even for rather small field sizes.</div>
</front>
</TEI>
<affiliations><list></list>
<tree><noCountry><name sortKey="Diem, Claus" sort="Diem, Claus" uniqKey="Diem C" first="Claus" last="Diem">Claus Diem</name>
<name sortKey="Gaudry, Pierrick" sort="Gaudry, Pierrick" uniqKey="Gaudry P" first="Pierrick" last="Gaudry">Pierrick Gaudry</name>
<name sortKey="Theriault, Nicolas" sort="Theriault, Nicolas" uniqKey="Theriault N" first="Nicolas" last="Thériault">Nicolas Thériault</name>
<name sortKey="Thome, Emmanuel" sort="Thome, Emmanuel" uniqKey="Thome E" first="Emmanuel" last="Thomé">Emmanuel Thomé</name>
</noCountry>
</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 006090 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006090 | 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é= CRIN:gaudry05b |texte= A double large prime variation for small genus hyperelliptic index calculus }}
This area was generated with Dilib version V0.6.33. |