L-notation

The L-notation is often used to express the computational complexity of certain algorithms for difficult number theory problems, eg. sieves for integer factorization and methods for solving discrete logarithms. 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$.

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.