4
$\begingroup$

It is well known that the time complexity of the number field sieve can be calculated by the formula $$\exp\big((C+o(1)) (\log n)^{1/3}(\log \log n)^{2/3}\big)$$

The constant C is known for the special and general number field sieve variants.
My question is, how can the value $o(1)$ be approximated for cryptographic reasonable values of n (e.g. $2^{1024} \le n \le 2^{4096}$)?
Do there exist known upper and lower bounds?

The reason for this question is as follows. By the definition of o(1) one can only conclude that asymptotically this value vanishes. But for any bounded value of n, the value can be anything. Therefore, in a strong mathematical sense, this formula is useless to conclude anything about real-size factorization problems.

$\endgroup$
6
  • $\begingroup$ @fgrieu: My intention was not to go into philosophical discussions. I simply wanted to know if there are concrete estimates for o(1). What is confusing you by this question? $\endgroup$
    – user27950
    Oct 8, 2016 at 7:03
  • $\begingroup$ Of course it's useless for real-size problems, it's an asymptotic complexity. And it would still be even if you removed the $o(1)$ term; how much "real life" time does one abstract "unit of complexity" in the formula above take? You're using the wrong tool to measure actual running time, you need to benchmark it on your hardware and see how long it takes for some reasonable sizes, and then possibly extrapolate it, maybe using the formula above as a guide of roughly how it scales... $\endgroup$
    – Thomas
    Oct 8, 2016 at 9:47
  • $\begingroup$ @Thomas: With the o(1) term it is not an asymptotic formula, but a formula valid for all n. Second, I do not want to compare hardware implementations but algorithms . $\endgroup$
    – user27950
    Oct 8, 2016 at 9:54
  • 1
    $\begingroup$ @Cryptostasis It really isn't, and no, you can't; you still have a hidden constant inherent to the asymptotic definition the formula represents (that is not the $C$ in your formula above) that you don't know. You can't use this formula to compare algorithms for any specific value of $n$, it is only useful as a measure of how different algorithms scale as $n$ increases. It is meaningless when instantiated with any specific value of $n$. $\endgroup$
    – Thomas
    Oct 8, 2016 at 9:59
  • $\begingroup$ Ok, then let's get pragmatic. The number field sieve is used to factor real sized problems. What sense does then an asymptotic formula make which cannot be applied to such problems? $\endgroup$
    – user27950
    Oct 8, 2016 at 10:02

2 Answers 2

1
$\begingroup$

Summary: it is common, and arguably safe, to assume that the $o(1)$ term is positive, and take it at zero, in circumstances where the formula is then used to estimate a lower bound of the ratio of work for larger value of $n$ to that for smaller values of $n$.


The formula given, with $o(1)$ term, gives the complexity of NFS. If modified by assigning a real value (say, zero) to the $o(1)$ term, it yields a function of $n$ without unit, thus insufficient to calculate the time (or effort, or cost) needed to run the algorithm for a given $n$. The $o(1)$ term happens to encompass the very order of magnitude of the cost (as a consequence of the outer exponential and the positive exponent to the $\log n$ term).

However, a common and legitimate use of that formula is to evaluate how the effort to run the NFS scales with $n$, by computing the ratio of what the formula gives for different values of $n$ (and taking the base-2 log for a security variation in bits). In that sense, it makes sense to ask which value of $o(1)$ should be used for a given $n$.

I don't know, and likely that depends on the variant of NFS (which also has a huge influence on $C$), and the hardware at hand.

However, a common approach is to hypothesize that this $o(1)$ term is positive, and take it as zero when extrapolating how larger $n$ needs to be, thus (if the hypothesis is correct) erring on the safe side from a key-holder's point of view.


Addition commenting the self-answer: an example of the practice in the previous paragraph is the formula given by the NIST in Implementation Guidance for FIPS PUB 140-2 and the Cryptographic Module Validation Program (updated August 1, 2016), computing the conventional bit strength $x$ of an RSA public modulus of $L$ bits as $$x\;=\;{1.923\times\sqrt[3]{L\log(2)}\times\sqrt[3]{(\log(L\log (2)))^2}-4.69\over\log(2)}$$ which is obtained by

  • straightforward transformation of the GNFS complexity formula using $C=\sqrt[3]{64\over9}$ rounded to 4 significant digits;
  • ignoring the $o(1)$ term, thus obtaining an $x$ such that $2^x$ is an estimation of work in unknown unit;
  • solving the above issue by introducing the additive constant $-4.69$ (which really is a multiplicative constant of $2^{-4.69/\log(2)}$ on the involved work $2^x$), determined so that when $L=1024=2^{10}$, the result obtained is $x=80.000\dots$, because that fits the FIPS 140-2 normative context, and anecdotal evidence suggests that the cost of breaking common 80-bit symmetric cryptography would be smaller than the cost of factoring a properly generated 1024-bit RSA modulus.

That formula thus arguably errs on the safe side from the key-holder's point of view if used to estimate the security given by an RSA modulus of $L\ge1024$ bits properly generated from true randomness, under the assumption that GNFS roughly as practiced now remains the best factoring algorithm.

$\endgroup$
5
  • $\begingroup$ What do you mean by "a function of n without unit" ? $\endgroup$
    – user27950
    Oct 8, 2016 at 17:55
  • $\begingroup$ @Cryptostasis: year (rotation of earth around sun) would be a unit; time of rotation of electron in an hydrogen atom another; number of elementary bit operations another (more reasonable) one. $\endgroup$
    – fgrieu
    Oct 8, 2016 at 18:04
  • $\begingroup$ I am not clear if I understand you correctly. I want to compare different algorithms by their complexity functions. The unit doesn't matter as long as one uses always the same units. $\endgroup$
    – user27950
    Oct 8, 2016 at 18:13
  • $\begingroup$ @Cryptostasis: indeed, the unit doesn't matter as long as one uses always the same units. Problem is, that particular formula has an unspecified multiplicative constant/unit, that matters to comparison, varies considerably between implementations, and is hidden/made pointless by the $o(1)$, which as $n$ grow matters more to the result than any multiplicative constant can. Thus you can use the formula, to some degree, to tell how $n$ changes the runtime for a given implementations; but not to predict the runtime without a reference, or compare different implementations. $\endgroup$
    – fgrieu
    Oct 8, 2016 at 23:07
  • $\begingroup$ Thank you for clarification and explaining the mysterious constant. $\endgroup$
    – user27950
    Oct 9, 2016 at 11:44
0
$\begingroup$

I think, I found an answer.

The Nist document Implementation Guidance for FIPS PUB 140-2 and the Cryptographic Module Validation Program contains on page 92 a formula where the bit strength of RSA is computed. The formula is obviously derived from the number field sieve complexity formula. It has the o(1) term omitted but instead a somewhat mysterious additional constant -4.69.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.