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, 2016
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 : jeudi 8 juin 2017 - 01:10:14
Document(s) archivé(s) le : vendredi 8 septembre 2017 - 12:13:17

Fichiers

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

Identifiants

  • HAL Id : hal-00954365, version 3

Collections

Citation

Razvan Barbulescu, Armand Lachand. Some mathematical remarks on the polynomial selection in NFS. Mathematics of Computation, American Mathematical Society, 2016. <hal-00954365v3>

Partager

Métriques

Consultations de
la notice

65

Téléchargements du document

46