Abstract - IPAM

Abstract

Searching for Higher-Degree Polynomials for the General Number Field Sieve

Peter Montgomery

Microsoft Research

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.
No video available
Back to Long Programs