L-notation

L-notation is an asymptotic notation analogous to big-O notation, denoted as $L_{n}[\alpha ,c]$ for a bound variable $n$ tending to infinity. Like big-O notation, it is usually used to roughly convey the computational complexity of a particular algorithm.

L-notation is used mostly in computational number theory, to express the complexity of algorithms for difficult number theory problems, eg. sieves for integer factorization and methods for solving discrete logarithms, because it is more concise than big-O in these contexts.

It is defined as

$L_{n}[\alpha ,c]=O\left(e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}\right)$,

where c is a positive constant, and $\alpha$ is a constant $0\leq \alpha \leq 1$.

When $\alpha$ is 0, then

$L_{n}[\alpha ,c]=L_{n}[0,c]=O\left(e^{(c+o(1))\ln \ln n}\right)=O((\ln n)^{c+o(1)})$

is a polynomial function of $\ln n$; when $\alpha$ is 1 then

$L_{n}[\alpha ,c]=L_{n}[1,c]=O\left(e^{(c+o(1))\ln n}\right)=O(n^{c+o(1)})$

is a fully exponential function of $\ln n$ (and thereby polynomial in $n$).

If $\alpha$ is between 0 and 1, the function is subexponential (and superpolynomial).

Examples

For the elliptic curve discrete logarithm problem, the fastest general purpose algorithm is the baby-step giant-step algorithm, which has a running time on the order of the square-root of the group order n. In L-notation this would be

$L_{n}[1,1/2]=O(n^{{\frac {1}{2}}+o(1)})$.

Current general-purpose integer factorization algorithms have subexponential time complexities. The general number field sieve is believed to have a running time of

$L_{n}[1/3,c]=O\left(e^{(c+o(1))(\ln n)^{\frac {1}{3}}(\ln \ln n)^{\frac {2}{3}}}\right)$

The existence of the AKS primality test which runs in polynomial time means that the time complexity for primality testing is known to be

$L_{n}[0,c]=O(n^{c+o(1)})$

where $c$ has been proven to be at most 6.

References

• Menezes, Alfred J., van Oorschot, Paul C., Vanstone, Scott A., Handbook of Applied Cryptography, CRC Press, Boca Raton, New York, London, Tokyo, 1996. ISBN 0-8493-8523-7.