Cubic Polynomials in the Number Field Sieve
Ronnie Scott Williams · 2010
In order to use the Number Field Sieve to factor an integer, N, two coprime, irreducible polynomials with a common root modulo N must be found. It is conjectured that there exist pairs of cubic polynomials with coefficients of size O(N1/6) = O(N3/18) for any choice of N, but this has yet to be proven. In this thesis, we provide a method for constructing two cubic polynomials with coefficients of size O(N2/9) = O(N4/18). This is achieved through a clever choice of common root and the use of the LLL-algorithm.