Discrete logarithm computations over finite fields using Reed-Solomon codes

Résumé : Cheng et Wan ont relié le décodage des codes de Reed-Solomon au calcul de logarithmes discrets dans les corps finis, dans le but de prouver la difficulté de leur décodage. Dans cet article, nous expérimentons le calcul de logarithmes discrets sur GF(q^h) en utilisant des codes de Reed-Solomon. Pour h fixé et q tendant vers l'infini, nous présentons un algorithme, appelé RSDL, qui requiert O~(h! q^2) opérations su GF(q), opérant sur une matrice qxq avec (h+2)q coefficients non-nuls. Nous donnons des variantes plus rapides, parmi lesquelles une version incrémentale et une autre utilisant des corps finis auxiliaires qui ne sont pas nécessairement des sous-corps du corps GF(q^h); cette variante est très pratique pour des valeurs modérées de q et h. Nous incluons également quelques résultats numériques obtenus avec notre première implantation.
Liste complète des métadonnées


https://hal.inria.fr/hal-00672050
Contributeur : François Morain <>
Soumis le : lundi 20 février 2012 - 14:21:56
Dernière modification le : vendredi 10 février 2017 - 01:12:45
Document(s) archivé(s) le : lundi 21 mai 2012 - 02:21:56

Fichiers

chwa.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00672050, version 1
  • ARXIV : 1202.4361

Collections

Citation

Daniel Augot, François Morain. Discrete logarithm computations over finite fields using Reed-Solomon codes. 2012. <hal-00672050>

Partager

Métriques

Consultations de
la notice

801

Téléchargements du document

298