L-notation

The L-notation is widely used to express the computational complexity of an algorithm. By definition

$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}[0,c]$

is a polynomial function of $\ln n$. When $\alpha$ is 1 then

$L_{n}[1,c]$

is a fully exponential function of $\ln n$.

Example

For the elliptic curve discrete log 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}})$.

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.