Selecting polynomials for the Function Field Sieve

Razvan Barbulescu 1
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Résumé : Le crible des corps de fonctions est un algorithme de calcul de logarithme discret dans un corps fini GF(q^n), où q est petit et puissance d'un nombre premier. L'objectif de cet article est la sélection de bons polynômes adaptés à cet algorithme. Pour cela on définit et on mesure les propriétés liées à la taille, à ce qu'on appelle "propriété de racines modulaires" et "propriété d'annulation des termes". On aboutit sur un algorithme qui permet de tester rapidement un grand nombre de polynômes. Notre étude permet également d'expliquer le comportement des polynômes inséparables et donne une façon simple de voir l'algorithme de Coppersmith comme un cas particulier du crible des corps de fonctions.
Type de document :
Article dans une revue
Mathematics of Computation, American Mathematical Society, 2015, 84 (296), pp.2987-3012 〈http://www.ams.org/journals/mcom/2015-84-296/S0025-5718-2015-02940-8/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00798386
Contributeur : Razvan Barbulescu <>
Soumis le : vendredi 8 mars 2013 - 14:45:02
Dernière modification le : jeudi 22 septembre 2016 - 14:31:07
Document(s) archivé(s) le : dimanche 9 juin 2013 - 08:20:07

Fichiers

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

Identifiants

  • HAL Id : hal-00798386, version 1
  • ARXIV : 1303.1998

Collections

Citation

Razvan Barbulescu. Selecting polynomials for the Function Field Sieve. Mathematics of Computation, American Mathematical Society, 2015, 84 (296), pp.2987-3012 〈http://www.ams.org/journals/mcom/2015-84-296/S0025-5718-2015-02940-8/〉. 〈hal-00798386〉

Partager

Métriques

Consultations de
la notice

375

Téléchargements du document

291