Some mathematical remarks on the polynomial selection in NFS
Résumé
In this work, we consider the proportion of smooth (free of large prime factors) values of a binary form $F(X_1,X_2)\in\mathbf{Z}[X_1,X_2]$. In a particular case, we give an asymptotic equivalent for this proportion which depends on $F$. This is related to Murphy's $\alpha$ function, which is known in the cryptographic community, but which has not been studied before from a mathematical point of view. Our result proves that, when $\alpha(F)$ is small, $F$ has a high proportion of smooth values. This has consequences on the first step, called polynomial selection, of the Number Field Sieve, the fastest algorithm of integer factorization.
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.
Origine : Fichiers produits par l'(les) auteur(s)