Some mathematical remarks on the polynomial selection in NFS

2014/03/02 by Barbulescu, Razvan, Lachand, Armand
#Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1403.0184

Abstract

In this work, we consider the proportion of smooth (free of large prime factors) values of a binary form F(X₁,X₂)∈\Z[X₁,X₂]. 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.

Related

• Selecting polynomials for the Function Field Sieve
• Montgomery's method of polynomial selection for the number field sieve
• Smooth numbers are orthogonal to nilsequences
• A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
• Lower Bounds for the Number of Smooth Values of a Polynomial