Skip to Main content Skip to Navigation
New interface
Journal articles

Some mathematical remarks on the polynomial selection in NFS

Razvan Barbulescu 1 Armand Lachand 2 
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.
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)

Identifiers

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⟩

Share

Metrics

Record views

324

Files downloads

466