Some mathematical remarks on the polynomial selection in NFS

Résumé : Dans cet article, nous étudions la proportion de valeurs friables (sans grands facteurs premiers) d'une forme binaire $F(X_1,X_2)\in\mathbf{Z}[X_1,X_2]$. Dans un cas particulier, nous prouvons un équivalent asymptotique de cette proportion qui dépend de $F$. Cela est lié à la fonction $\alpha$ de Murphy, qui est connu à la communauté cryptographique, mais qui n'a pas été étudiée précédemment avec des outils mathématiques. Notre résultat montre que, si $\alpha(F)$ est petit, alors $F$ a un grand nombre de valeurs friables. Cela a des conséquences sur la première étape, appelée sélection polynomiale, du crible algébrique (NFS), meilleur algorithme de factorisation d'entiers.
Type de document :
Article dans une revue
Mathematics of Computation, American Mathematical Society, 2017, 86, pp.397-418. 〈10.1090/mcom/3112 〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00954365
Contributeur : Razvan Barbulescu <>
Soumis le : mercredi 7 juin 2017 - 10:59:10
Dernière modification le : mardi 24 avril 2018 - 13:55:00
Document(s) archivé(s) le : vendredi 8 septembre 2017 - 12:13:17

Fichiers

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

Identifiants

Citation

Razvan Barbulescu, Armand Lachand. Some mathematical remarks on the polynomial selection in NFS. Mathematics of Computation, American Mathematical Society, 2017, 86, pp.397-418. 〈10.1090/mcom/3112 〉. 〈hal-00954365v3〉

Partager

Métriques

Consultations de la notice

200

Téléchargements de fichiers

107