Proportion of RSA moduli factorable by NFS with less effort than average?

Question

When applied to integers $N$ of comparable size, the Number Field Sieve is notoriously much faster if $N$ is known to be of the form $r^k\pm s$ with $r$ and $s$ suitably small integers, and $k$ an integer: using $L$-notation, the running time of this Special NFS is $L_N(1/3,\sqrt[3]{32/9})$, versus $L_N(1/3,\sqrt[3]{64/9})$ for the General NFS. Correspondingly, public factoring records are higher for SNFS than GNFS (1199 versus 768 bits at time of writing).

GNFS is applicable to most RSA public moduli; but there is some small odd that SNFS is applicable to a random RSA public moduli; and perhaps a more sizable odd that some speedup of NFS is enabled by a suitable form of $N$ (perhaps more general than for the original SNFS).

I'm asking for an evaluation of the proportion of RSA moduli of $n$ bits factorable by NFS with $\alpha\ll1$ times the average GNFS effort.

If that proportion was sizable, and the time to identify such moduli not an insurmountable obstacle, that could matter to situations (which abound) where a potential adversary is content with factoring any of many RSA moduli.

Answer 1

The core difference between the SNFS and the GNFS is that the polynomials $f(x)$ and $g(x)$ for the SNFS have short coefficients, where typically the largest coefficient of $f$ is $O(1)$ and the largest coefficient of $g$ is $O(n^{1/(d + 1)})$. On the GNFS, coefficients are typically closer to $n^{1/(d+1)}$ on both sides, which results in much larger integers to test for smoothness.

So the question is: for a randomly selected integer $n$, can we find a set of polynomials, plus a shared root $m$ modulo $n$, such that their coefficients are significantly smaller than average? The answer is somewhat unsatisfying. I'll exemplify with a simple unsophisticated example, but the principle holds in general.

There are many polynomials that can fit the bill, if we don't restrict their size too much. If we let coefficients be bounded by $n^{1/(d+1)}$, then we have $n^{(d+2)/(d+1)}$ possible $f(x)$ polynomials and shared root, $n^{1/(d+1)}$ of which satisfy $f(m) = 0 \bmod n$. This would be $2^{146}$ for $n \approx 2^{1024}$ and $d = 6$.

But what happens when we try to approximate to the SNFS, by keeping $m$ fixed but reducing the coefficients of $f$? Assuming coefficients are uniformly and independently distributed, the number of available polynomials starts decreasing proportionally to the factor we want to reduce them by. For example, for $n \approx 2^{1024}$ and $d = 6$, as before, if we want to reduce coefficients from $\approx 170$ bits to $\approx 170 - 20 = 150$ bits, we find that there are only $2^{146} / (2^{20})^{6+1} \approx 78$ suitable polynomials! Significantly bigger reductions would be unlikely to exist at all, except for a few rare cases, like SNFS-friendly numbers.

All of the above was simply a counting exercise. But the idea is simple—polynomials with small coefficients, which also satisfy the GNFS requirements, are vastly outnumbered by the number of integers to factor.

Even so, it would be great to be able to find optimal polynomials for any integer $n$, even if they don't approach SNFS quality. But we don't really know how to find such optimal polynomials other than essentially brute force search and some heuristic techniques, which are nevertheless very much worth it. Given the mismatch between lower bounds and current algorithms, if the state of the art of polynomial selection were to suddenly improve significantly the answer to your question would be "every modulus".

In case I failed to convey the argument, I'll refer to §12.12 of Buhler et al., §4 Bernstein and Lenstra, §2.3.2 Murphy, §2.2.4 Coxon, or §6.2.7 Crandall and Pomerance, all of which discuss this polynomial selection issue.

Some fine print: size is not the only factor in practice to select a good polynomial. In particular, having many roots modulo small primes seems to help in finding smooth numbers. But as far as asymptotics are concerned, size is the only factor we're concerned with.