Some mathematical remarks on the polynomial selection in NFS
This work provides mathematical insights for cryptographers and researchers in computational number theory, but it is incremental as it builds on known concepts like Murphy's α function.
The authors tackled the problem of analyzing the proportion of smooth values of a binary form in integer factorization, proving that when Murphy's α function is small, the form has a high proportion of smooth values, which impacts polynomial selection in the Number Field Sieve.
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\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 $α$ 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 $α(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.