Non-linear polynomial selection for the number field sieve

We present an algorithm to find two non-linear polynomials for the Number Field Sieve integer factorization method. This algorithm extends Montgomery’s “two quadratics” method; for degree 33, it gives two skewed polynomials with resultant O(N5/4)O(N5/4), which improves on the Williams O(N4/3)O(N4/3) result (Williams, 2010).

► We present a new algorithm to find two non-linear polynomials for NFS.
► This algorithm extends Montgomery’s “two quadratics” method.
► For degree 3, it gives two skewed polynomials with resultant O(N5/4)O(N5/4).
► This improves on the Williams O(N4/3)O(N4/3) result (Williams, 2010).