Montgomery's method of polynomial selection for the number field sieve
This work addresses polynomial selection for factoring large integers, which is incremental as it builds on Montgomery's existing method.
The paper analyzes Montgomery's method for polynomial selection in the number field sieve, which is used to factor large integers, and examines the existence of suitable geometric progressions for this purpose.
The number field sieve is the most efficient known algorithm for factoring large integers that are free of small prime factors. For the polynomial selection stage of the algorithm, Montgomery proposed a method of generating polynomials which relies on the construction of small modular geometric progressions. Montgomery's method is analysed in this paper and the existence of suitable geometric progressions is considered.