3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So, if I get you correctly, because there are so few friendly polynomials, chances that one exists applicable to a randomly selected 1024-bit RSA moduli are negligible; hence for $α=1/2$ (halving the work due to the modulus allowing use of a friendly polynomial) the proportion of the question is negligible for practical purposes (says $<2^{-30}$ )? $\endgroup$ – fgrieu Aug 25 '16 at 8:06
  • $\begingroup$ $\alpha = 0.5$ is definitely achievable by spending more time in polynomial selection, or by fine-tuning the process a bit. The improvements I'm thinking about would be for an $\alpha$ very far away from 1, say, a factor of $2^{10}$ or higher. Note that beyond obviously structured integers, it is hard to predict whether an integer will yield a better polynomial than another. $\endgroup$ – Samuel Neves Aug 25 '16 at 8:17
  • $\begingroup$ Lowering work to $α=2^{-10}$ (or even $2^{-5}$) is highly desirable in practice; for 1024-bit modulus (still widely used) and a practical attacker, that could be the difference between feasible or not. And, in practice, an attacker has often many moduli to choose from (factoring the modulus of any trusted CA surreptitiously brings one in that club; factoring the modulus on any device trusted to perform X with some limitation allows to perform X without the limitation). Thus, the question remains of some interest. $\endgroup$ – fgrieu Aug 25 '16 at 8:32
  • 1
    $\begingroup$ I do not disagree. But besides the asymptotics above, the situation that we have is that we can't easily tell whether a number will yield a better poly than another without running the process on both, and the differences aren't usually huge anyway. So given a group of moduli, we could run poly selection on all of them, and then proceed with the one with the better polynomial. But since poly selection is computationally expensive, for a large group of moduli (> 10-20), this would be slower than factoring a an arbitrary one! $\endgroup$ – Samuel Neves Aug 25 '16 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.