Skip to Main content Skip to Navigation
New interface

# Some mathematical remarks on the polynomial selection in NFS

1 CARAMBA - Cryptology, arithmetic : algebraic methods for better algorithms
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : 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.
Document type :
Journal articles
Domain :
Complete list of metadata

https://hal.inria.fr/hal-00954365
Contributor : Razvan Barbulescu Connect in order to contact the contributor
Submitted on : Wednesday, June 7, 2017 - 10:59:10 AM
Last modification on : Friday, July 8, 2022 - 10:10:16 AM
Long-term archiving on: : Friday, September 8, 2017 - 12:13:17 PM

### Files

finalversion.pdf
Files produced by the author(s)

### Citation

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

Record views

Files downloads