Improvements to the number field sieve for non-prime finite fields

Razvan Barbulescu 1 Pierrick Gaudry 1 Aurore Guillevic 2, 3 François Morain 3, *
* Auteur correspondant
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Résumé : Nous décrivons plusieurs stratégies pour accélérer le calcul de logarithmes discrets dans un corps fini non premier de caractéristique moyenne ou grande à l'aide du crible algébrique. Parmi elles, de nouvelles méthodes de sélection polynomiale; l'utilisation explicite d'automorphismes; des calculs explicites dans les corps de nombres; et la prédiction de l'annulation des logarithmes virtuels d'unités bien choisies. D'un point de vue théorique, nous obtenons une complexité nouvelle en $L_{p^n}(1/3,\sqrt[3]{96/9})$ dans le cas de la caractéristique moyenne. Du côté pratique, nous avons mené à bien le calcul de logarithmes discrets dans $F_{p^2}$ avec $p$ premier de $80$ chiffres décimaux.
Type de document :
Pré-publication, Document de travail
2014
Liste complète des métadonnées

https://hal.inria.fr/hal-01052449
Contributeur : Aurore Guillevic <>
Soumis le : vendredi 28 novembre 2014 - 19:05:25
Dernière modification le : vendredi 10 février 2017 - 01:13:12

Fichiers

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

Identifiants

  • HAL Id : hal-01052449, version 4
  • ARXIV : 1408.0718

Citation

Razvan Barbulescu, Pierrick Gaudry, Aurore Guillevic, François Morain. Improvements to the number field sieve for non-prime finite fields. 2014. <hal-01052449v4>

Partager

Métriques

Consultations de
la notice

476

Téléchargements du document

313