3 ms·
The first step in the number field sieve is to represent the number to be factored as a polynomial (two, in fact), and it is assumed in the following steps that
by pbsd 8y ago
The first step in the number field sieve is to represent the number to be factored as a polynomial (two, in fact), and it is assumed in the following steps that these polynomials do not split. If these polynomials did split with reasonable probability, the number field sieve would be a lot shorter.
The usual reference for this is Brilhart et al. [1], which deals with polynomial representations in arbitrary bases, as opposed to strictly base 2, as is the case here.
[1] https://doi.org/10.4153/CJM-1981-080-0 https://doi.org/10.4153/CJM-1981-080-0