What is the relation between these two descriptions of General Number Field Sieve?

Question

I am reading about General Number Field Sieve (GNFS) algorithm and its implementations, and the literature seems to have two different versions of the algorithm, but I can't find how these two are related. Is one an improvement over another? Or are they both used in practice? I just can't find any article or anything that would acknowledge existence of both... I found plenty of articles that follow one of the variants, I link some of them below.

Variant 1: A single polynomial $f\in \mathbb{Z}[x]$ is chosen and is then used to sieve integer pairs $(a,b)$ such that $a+\theta b$ is smooth over some algebraic factor base and at the same time $a+bm$ is smooth over some rational factor base.

• Lattice sieving and trial division, Golliver, Lenstra & McCurley, 1994, https://link.springer.com/chapter/10.1007/3-540-58691-1_38

• A Tale of Two Sieves, Pomerance, 1996, https://www.ams.org/notices/199612/pomerance.pdf

• An Introduction to the General Number Field Sieve, Matthew E. Briggs, 1998, https://personal.math.vt.edu/brown/doc/briggs_gnfs_thesis.pdf

• The number field sieve, Peter Stevenhagen, 2005, https://www.researchgate.net/publication/267068398_The_number_field_sieve

versus

Variant 2: A pair of polynomials $f_1,f_2\in \mathbb{Z}[x]$ is chosen and is then used to sieve integer pairs $(a,b)$ such that $a+b\theta_1$ is smooth over some algebraic factor base $B_1$ and at the same time $a+b\theta_2$ is smooth over some (another) algebraic factor base.

• Factorization of a 512–bit RSA Modulus, Cavallar, Dodson, Lenstra, ..., 2000, https://link.springer.com/chapter/10.1007/3-540-45539-6_1

• On Polynomial Selection for the General Number Field Sieve, Kleinjung, 2006, https://www.jstor.org/stable/4100137

• Polynomial selection in number field sieve for integer factorization, Pandey, Pal, 2016, https://www.sciencedirect.com/science/article/pii/S2213020916300210

• https://en.wikipedia.org/wiki/General_number_field_sieve (yes, wikipedia...)

I am just trying to reconcile what is the relation between these two methods, and why there seems to be no comparison or reference between the two (at least to my current search). I've been toying with some implementations such as CADO-NFS and I know it uses the second variant, so it might seem it was a historical improvement over the first one. But in that case, wouldn't there be an article describing this new and more efficient version? Help me understand what I am missing...

Answer 1

I think I found a link actually in one of the references above, in A Tale of Two Sieves by Carl Pomerance, on page 1484:

Several variations on the basic idea of the number field sieve show some promise. One can replace the linear expression $a − mb$ used in the number field sieve with $b^k g(a/b)$, where $g(x)$ is an irreducible polynomial over $\mathbb{Z}$ of degree $k$ with $g(m)\equiv 0 \pmod{n}$. That is, we use two polynomials $f(x)$, $g(x)$ with a common root $m\bmod n$ (the original scenario has us take $g(x) = x − m$). It is a subject of current research to come up with good strategies for choosing polynomials.

From the link there we can find two articles A multiple polynomial general number field sieve and An implementation of the number field sieve by M. Elkenbracht-Huizing from 1996. So these two seem to be first published works using the two polynomials variation which was then used afterwards (although some later materials later still refer the original variant described by Pomerance).