1
$\begingroup$

I'm told that General Number Field Sieve works with computational complexity $e^{\sqrt[3]{\frac{64}{9}+o(1)}\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}$. However, without some computation work it should run with computational complexity $e^{\sqrt[3]{3+o(1)}\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}$.

This does not seem to be as a big difference but according to the following table it is:

enter image description here

How can be the difference so huge if only a constant changes?

$\endgroup$

1 Answer 1

1
$\begingroup$

By moving the $o(1)$ and using elementary algebra, the formulas given can be rewritten with a single digit difference, as $$\left(e^{(3^{-2/3})\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}\right)^{4+o(1)}\;\text{ and }\;\left(e^{(3^{-2/3})\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}\right)^{3+o(1)}$$

Two things are now apparent:

  1. The exponent changes from about 4 to about 3; this qualitatively explains why there is such an enormous gap.
  2. The $o(1)$ beats any outer multiplicative factor, and the formulas are thus missing some unknown, possibly large multiplicative factor when we use them for any particular $n$. This explains why we can at best use the formulas to predict approximately how the run time of each of the attacks (or the ratio of the two run times) scales with $n$ (and then, not rigorously); but not to quantitatively predict the relative runtime of the two algorithms for some $n$.
$\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.

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