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(e^{((c + o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha})})](../../../math/1/e/e/1ee252dc36080fac68de8276f689dbb4.png)
,
where c is a positive constant, and α is a constant 0 < α < 1.
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.
