General Number Field Sieve Big O Clarification

Question

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?

Answer 1

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)$.