Algorithms of discrete logarithm in finite fields
Identifieur interne : 000C12 ( Hal/Corpus ); précédent : 000C11; suivant : 000C13Algorithms of discrete logarithm in finite fields
Auteurs : Razvan BarbulescuSource :
Descripteurs français
- mix :
Abstract
In this thesis we study at length the discrete logarithm problem in finite fields. In the first part, we focus on the notion of smoothness and on ECM, the fastest known smoothness test. We present an improvement to the algorithm by analyzing the Galois properties of the division polynomials. We continue by an application of ECM in the last stage of the number field sieve (NFS). In the second part, we present NFS and its related algorithm on function fields (FFS). We show how to speed up the computation of discrete logarithms in all the prime finite fields of a given bit-size by using a pre-computation. We focus later on the polynomial selection stage of FFS and show how to compare arbitrary polynomials with a unique function. We conclude the second part with an algorithm issued from the recent improvements for discrete logarithm. The key fact was to create a descent procedure which has a quasi-polynomial number of nodes, each requiring a polynomial time. This leads to a quasi-polynomial algorithm for finite fields of small characteristic.
Url:
Links to Exploration step
Hal:tel-00925228Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Algorithms of discrete logarithm in finite fields</title><title xml:lang="fr">Algorithmes de logarithmes discrets dans les corps finis</title><author><name sortKey="Barbulescu, Razvan" sort="Barbulescu, Razvan" uniqKey="Barbulescu R" first="Razvan" last="Barbulescu">Razvan Barbulescu</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-119560" status="VALID"><idno type="RNSR">201020971F</idno><orgName>Cryptology, Arithmetic: Hardware and Software</orgName><orgName type="acronym">CARAMEL</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/caramel</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423083" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName><orgName type="acronym">LORIA - ALGO</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:tel-00925228</idno><idno type="halId">tel-00925228</idno><idno type="halUri">https://tel.archives-ouvertes.fr/tel-00925228</idno><idno type="url">https://tel.archives-ouvertes.fr/tel-00925228</idno><date when="2013-12-05">2013-12-05</date><idno type="wicri:Area/Hal/Corpus">000C12</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Algorithms of discrete logarithm in finite fields</title><title xml:lang="fr">Algorithmes de logarithmes discrets dans les corps finis</title><author><name sortKey="Barbulescu, Razvan" sort="Barbulescu, Razvan" uniqKey="Barbulescu R" first="Razvan" last="Barbulescu">Razvan Barbulescu</name><affiliation><hal:affiliation type="researchteam" xml:id="struct-119560" status="VALID"><idno type="RNSR">201020971F</idno><orgName>Cryptology, Arithmetic: Hardware and Software</orgName><orgName type="acronym">CARAMEL</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/caramel</ref></desc><listRelation><relation active="#struct-129671" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-423083" type="direct"></relation><relation active="#struct-206040" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation><tutelles><tutelle active="#struct-129671" type="direct"><org type="laboratory" xml:id="struct-129671" status="VALID"><idno type="RNSR">198618246Y</idno><orgName>INRIA Nancy - Grand Est</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/nancy</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-423083" type="direct"><org type="department" xml:id="struct-423083" status="VALID"><orgName>Department of Algorithms, Computation, Image and Geometry</orgName><orgName type="acronym">LORIA - ALGO</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.loria.fr/la-recherche-en/departements/algorithmics</ref></desc><listRelation><relation active="#struct-206040" type="direct"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-413289" type="indirect"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation></listRelation></org></tutelle><tutelle active="#struct-206040" type="indirect"><org type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno><idno type="RNSR">198912571S</idno><idno type="IdUnivLorraine">[UL]RSI--</idno><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><date type="start">2012-01-01</date><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-413289" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="direct"></relation></listRelation></org></tutelle><tutelle active="#struct-413289" type="indirect"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno><idno type="IdUnivLorraine">[UL]100--</idno><orgName>Université de Lorraine</orgName><orgName type="acronym">UL</orgName><date type="start">2012-01-01</date><desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.univ-lorraine.fr/</ref></desc></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno><idno type="IdRef">02636817X</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle></tutelles></hal:affiliation></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="fr"><term>corps finis</term><term>courbes elliptiques</term><term>cryptographie</term><term>cryptography</term><term>discrete logarithm</term><term>elliptique curves</term><term>finite fields</term><term>logarithme discret</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">In this thesis we study at length the discrete logarithm problem in finite fields. In the first part, we focus on the notion of smoothness and on ECM, the fastest known smoothness test. We present an improvement to the algorithm by analyzing the Galois properties of the division polynomials. We continue by an application of ECM in the last stage of the number field sieve (NFS). In the second part, we present NFS and its related algorithm on function fields (FFS). We show how to speed up the computation of discrete logarithms in all the prime finite fields of a given bit-size by using a pre-computation. We focus later on the polynomial selection stage of FFS and show how to compare arbitrary polynomials with a unique function. We conclude the second part with an algorithm issued from the recent improvements for discrete logarithm. The key fact was to create a descent procedure which has a quasi-polynomial number of nodes, each requiring a polynomial time. This leads to a quasi-polynomial algorithm for finite fields of small characteristic.</div></front></TEI><hal api="V3"><titleStmt><title xml:lang="en">Algorithms of discrete logarithm in finite fields</title><title xml:lang="fr">Algorithmes de logarithmes discrets dans les corps finis</title><author role="aut"><persName><forename type="first">Razvan</forename><surname>Barbulescu</surname></persName><email>razvan.barbulescu@inria.fr</email><ptr type="url" target="http://www.loria.fr/~barbules/index.html"></ptr><idno type="halauthor">825440</idno><affiliation ref="#struct-119560"></affiliation></author><editor role="depositor"><persName><forename>Razvan</forename><surname>Barbulescu</surname></persName><email>razvan.barbulescu@inria.fr</email></editor></titleStmt><editionStmt><edition n="v1" type="current"><date type="whenSubmitted">2014-01-07 17:06:27</date><date type="whenModified">2015-12-16 01:09:17</date><date type="whenReleased">2014-01-09 13:33:53</date><date type="whenProduced">2013-12-05</date><date type="whenEndEmbargoed">2014-01-07</date><ref type="file" target="https://tel.archives-ouvertes.fr/tel-00925228/document"><date notBefore="2014-01-07"></date></ref><ref type="file" n="1" target="https://tel.archives-ouvertes.fr/tel-00925228/file/these_avec_resume.pdf"><date notBefore="2014-01-07"></date></ref></edition><respStmt><resp>contributor</resp><name key="172254"><persName><forename>Razvan</forename><surname>Barbulescu</surname></persName><email>razvan.barbulescu@inria.fr</email></name></respStmt></editionStmt><publicationStmt><distributor>CCSD</distributor><idno type="halId">tel-00925228</idno><idno type="halUri">https://tel.archives-ouvertes.fr/tel-00925228</idno><idno type="halBibtex">barbulescu:tel-00925228</idno><idno type="halRefHtml">Cryptography and Security [cs.CR]. Université de Lorraine, 2013. English</idno><idno type="halRef">Cryptography and Security [cs.CR]. Université de Lorraine, 2013. English</idno></publicationStmt><seriesStmt><idno type="stamp" n="CNRS">CNRS - Centre national de la recherche scientifique</idno><idno type="stamp" n="INRIA">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="INRIA-LORRAINE">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LORIA2">Publications du LORIA</idno><idno type="stamp" n="INRIA-NANCY-GRAND-EST">INRIA Nancy - Grand Est</idno><idno type="stamp" n="LORIA-ACGI" p="LORIA">Algorithmique, calcul, image et géométrie</idno><idno type="stamp" n="LORIA">LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications</idno><idno type="stamp" n="UNIV-LORRAINE">Université de Lorraine</idno><idno type="stamp" n="INRIA_TEST">INRIA - Institut National de Recherche en Informatique et en Automatique</idno><idno type="stamp" n="LORIA-ALGO-TEST5">LORIA-ALGO-TEST5 </idno><idno type="stamp" n="INRIA2">INRIA 2</idno></seriesStmt><notesStmt></notesStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Algorithms of discrete logarithm in finite fields</title><title xml:lang="fr">Algorithmes de logarithmes discrets dans les corps finis</title><author role="aut"><persName><forename type="first">Razvan</forename><surname>Barbulescu</surname></persName><email>razvan.barbulescu@inria.fr</email><ptr type="url" target="http://www.loria.fr/~barbules/index.html"></ptr><idno type="halAuthorId">825440</idno><affiliation ref="#struct-119560"></affiliation></author></analytic><monogr><imprint><date type="dateDefended">2013-12-05</date></imprint><authority type="institution">Université de Lorraine</authority><authority type="school">Ecole Doctorale IAEM Lorraine (Informatique, Automatique, Électronique - Électrotechnique, Mathématiques)</authority><authority type="supervisor">Pierrick Gaudry(pierrick.gaudry@gmail.com)</authority><authority type="jury">Rapporteurs : Jean-Marc Couveignes Prof. Univers. Bordeaux</authority><authority type="jury">Alfred Menezes Prof. Univers. Waterloo, Canada</authority><authority type="jury">Examinateurs : Nicolas Brisebarre CR CNRS</authority><authority type="jury">Emmanuel Jeandel Prof. Univers. Lorraine</authority><authority type="jury">Antoine Joux Prof. Univers. Paris 6</authority><authority type="jury">François Morain Prof. École Polytechnique</authority><authority type="jury">Frederik Vercauteren KU Leuven, België</authority><authority type="jury">Directeur : Pierrick Gaudry DR CNRS</authority></monogr></biblStruct></sourceDesc><profileDesc><langUsage><language ident="en">English</language></langUsage><textClass><keywords scheme="author"><term xml:lang="fr">cryptography</term><term xml:lang="fr">discrete logarithm</term><term xml:lang="fr">finite fields</term><term xml:lang="fr">elliptique curves</term><term xml:lang="fr">cryptographie</term><term xml:lang="fr">logarithme discret</term><term xml:lang="fr">corps finis</term><term xml:lang="fr">courbes elliptiques</term></keywords><classCode scheme="halDomain" n="info.info-cr">Computer Science [cs]/Cryptography and Security [cs.CR]</classCode><classCode scheme="halTypology" n="THESE">Theses</classCode></textClass><abstract xml:lang="en">In this thesis we study at length the discrete logarithm problem in finite fields. In the first part, we focus on the notion of smoothness and on ECM, the fastest known smoothness test. We present an improvement to the algorithm by analyzing the Galois properties of the division polynomials. We continue by an application of ECM in the last stage of the number field sieve (NFS). In the second part, we present NFS and its related algorithm on function fields (FFS). We show how to speed up the computation of discrete logarithms in all the prime finite fields of a given bit-size by using a pre-computation. We focus later on the polynomial selection stage of FFS and show how to compare arbitrary polynomials with a unique function. We conclude the second part with an algorithm issued from the recent improvements for discrete logarithm. The key fact was to create a descent procedure which has a quasi-polynomial number of nodes, each requiring a polynomial time. This leads to a quasi-polynomial algorithm for finite fields of small characteristic.</abstract><abstract xml:lang="fr">Dans cette thèse nous examinons en détail le problème du logarithme discret dans les corps finis. Dans la première partie, nous nous intéressons à la notion de friabilité et à l'algorithme ECM, le plus rapide test de friabilité connu. Nous présentons une amélioration de l'algorithme en analysant les propriétés galoisiennes des polynômes de division. Nous continuons la présentation par une application d'ECM dans la dernière étape du crible algébrique (NFS). Dans la deuxième partie, nous présentons NFS et son algorithme correspondant utilisant les corps de fonctions (FFS). Parmi les améliorations examinées, nous montrons qu'on peut accélérer le calcul de logarithme discret au prix d'un pré-calcul commun pour une plage de premiers ayant le même nombre de bits. Nous nous concentrons ensuite sur la phase de sélection polynomiale de FFS et nous montrons comment comparer des polynômes quelconques à l'aide d'une unique fonction. Nous concluons la deuxième partie avec un algorithme issu des récentes améliorations du calcul de logarithme discret. Le fait marquant est la création d'une procédure de descente qui a un nombre quasi-polynomial de nœuds, chacun exigeant un temps polynomial. Cela a conduit à un algorithme quasi-polynomial pour les corps finis de petite caractéristique.</abstract></profileDesc></hal></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C12 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 000C12 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Hal
|étape= Corpus
|type= RBID
|clé= Hal:tel-00925228
|texte= Algorithms of discrete logarithm in finite fields
}}
| This area was generated with Dilib version V0.6.33. |  |