Batch Numeric Field Sieve [pdf]

Before people read too much into this, these results are purely asymptotic. It is hard to predict if they have any practical impact in the actual factorization of RSA keys (I'm not second-guessing the authors here; this is also clearly stated in the paper), since there may be huge constant factors hidden within the o(1).

For example, using sieving or the ECM inside the classic NFS has the same (in the RAM metric) L[1/3, 1.92 + o(1)] complexity. However, sieving is far more efficient in practice (in typical hardware), and has been the method of choice for decades. The batch NFS, like Coppersmith's factorization factory, cannot use sieving but only ECM (or some similar smoothness-detection method), so the constant factor involved here for useful sizes (e.g., 1024) is unknown.

The core difference between the batch NFS and Coppersmith is how relations on the rational side are handled. Coppersmith simply precomputes an `m` coefficient for a certain integer size, and precomputes all the necessary smooth relations `a - bm` for that `m`. The batch NFS is somewhat cleverer: it selects an `m` for a set of known integers of similar size, but then computes and discards relations that are not useful on either `a - bm` or `a - bα`, aka the rational and algebraic sides, for every integer in the set. The space savings here are huge, hence the massively improved AT cost. The computational savings are also large, especially given the mesh sorting tricks also used in DJB's 2001 circuit NFS [2].

A related recent work is the Mersenne factorization factory [1], which also used Coppersmith in a clever way to save time on multiple related factorizations.

[1] https://eprint.iacr.org/2014/653

[2] http://cr.yp.to/nfscircuit.html

PS: It is the number field sieve, not the numeric field sieve. I suppose the latter is the result of poor translation.