The Number Field Sieve is asymptotically the fastest algorithm for factoring a large integer N with no small prime factors, such as an RSA modulus. An early step in the algorithm selects two polynomials with a common root modulo N and “small” coefficients. We know ways to select two polynomials when one is linear, but that choice causes one polynomial norm to be much larger than the other. This talk says what is known about higher-degree selections, esp. a search for two cubic polynomials.
Copyright. All Rights Reserved.