L-notation
From Wikipedia, the free encyclopedia
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)](../../../../math/d/d/c/ddc1f5c159e9730b9eb3c76b139e7d8e.png)
,
where c is a positive constant, and α is a constant 
.
When α is 0, then
- Ln[0,c]
is a polynomial function of lnn. When α is 1 then
- Ln[1,c]
is a fully exponential function of lnn.
[edit] 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}})](../../../../math/c/6/b/c6b0c3cf817050bcc3378820e41f8bdf.png)
.
[edit] 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.
