1
$\begingroup$

This paper states that the general number field sieve is of order:

$$L\approx\exp\left((64/9)^{1/3}\,n^{1/3}\,(\ln(n))^{2/3}\right)$$

However several sources (e.g. Wolfram) give it as:

$$O\left( \exp\left((64/9)^{1/3}\,(\log n)^{1/3}\,(\log\log n)^{2/3}\right) \right)$$

To my knowledge L-notation and big O notation are exactly the same, so is this paper incorrect, or am I missing something?

It also gives the binary length of the number being factored, $n$, as being converted from its decimal length via:

$$n=k\,\ln(10)$$

I'm aware that if you can multiply by a constant factor then how the complexity is expressed doesn't matter (e.g. you can pick any log base so long as you're consistent), but since the correct way of doing this would be:

$$n = \lfloor k\, \log_2(10)\rfloor + 1$$

Is their stated conversion to $n$ acceptable?

$\endgroup$
  • $\begingroup$ There should be big $N$ in Wolfram notation. It's the number itself. $\endgroup$ – rus9384 Jul 7 '17 at 21:50
2
$\begingroup$

There is a small difference between these two:

  1. $L\approx\exp\left((64/9)^{1/3}\,n^{1/3}\,(\ln(n))^{2/3}\right)$. Here $n$ is a number of bits needed to represent given number $N$.

  2. $O\left( \exp\left((64/9)^{1/3}\,(\log N)^{1/3}\,(\log\log N)^{2/3}\right) \right)$. Here the number $N$ itself is used in notation.

This is true since length of number grows logarithmically of the number itself. Just put $n$ instead of $\log N$ or vice versa and you see that they are equal.

In terms of big O notation constants are uninteresing, so, base of logarithm also is uninteresting. That's why it doesn't make sense whether you interpret number in decimal or binary or any other (except unary) system.

$n=k\,\ln(10)$: here $\ln(10)$ is constant and we can get rid of it. Also, $k$ depends linearly on $n$, so $k = O(n)$.

$n = \lfloor k\, \log_2(10)\rfloor + 1$: and here both $\log_2(10)$ and $+1$ are removed when written as big O: it still equals $O(n)$.

$\endgroup$

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.