L-notation

---

title: "L-notation" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["asymptotic-analysis", "computational-complexity-theory"] description: "Notation describing limiting behavior in computational number theory" topic_path: "technology/computing" source: "https://en.wikipedia.org/wiki/L-notation" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Notation describing limiting behavior in computational number theory ::

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 rate of growth of a function, such as the computational complexity of a particular algorithm.

Definition

It is defined as

:L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}

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

L-notation is used mostly in computational number theory, to express the complexity of algorithms for difficult number theory problems, e.g. sieves for integer factorization and methods for solving discrete logarithms. The benefit of this notation is that it simplifies the analysis of these algorithms. The e^{c(\ln n)^\alpha(\ln\ln n)^{1-\alpha}} expresses the dominant term, and the e^{o(1)(\ln n)^\alpha(\ln\ln n)^{1-\alpha}} takes care of everything smaller. Many advanced number theory algorithms have not been fully studied and not much is definitely known about their complexity and behaviour. The breadth of L-notation, allowing one to span polynomial to exponential growth rates, and its looseness, allowing theorems and heuristic analyses to be made more easily, have made its use popular in this relatively niche field.

When \alpha is 0, then

:L_n[\alpha,c] = L_n[0, c] = e^{(c + o(1)) \ln\ln n} = (\ln n)^{c + o(1)},

is a polylogarithmic function (a polynomial function of ln n);

When \alpha is 1 then

:L_n[\alpha,c] = L_n[1, c] = e^{(c + o(1)) \ln n} = 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 of ln n (and superpolynomial).

Examples

Many general-purpose integer factorization algorithms have subexponential time complexities. The best is the general number field sieve, which has an expected running time of

:L_n[1/3, c] = e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}

for c = (64/9)^{1/3} \approx 1.923. The best such algorithm prior to the number field sieve was the quadratic sieve which has running time

:L_n[1/2, 1] = e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.,

the third-fastest known factoring method: Lenstra elliptic-curve factorization , which has running time

:L_n[1/2, 2^{1/2}] = e^{(2^{1/2}+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.,

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] = n^{1/2+o(1)}.,

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

:L_n[0, c] = (\ln n)^{c+o(1)},

where c has been proven to be at most 6.

History

L-notation has been defined in various forms throughout the literature. The first use of it came from Carl Pomerance in his paper "Analysis and comparison of some integer factoring algorithms". This form had only the c parameter: the \alpha in the formula was 1/2 for the algorithms he was analyzing. Pomerance had been using the letter L (or lower case l) in this and previous papers for formulae that involved many logarithms.

The formula above involving two parameters was introduced by Arjen Lenstra and Hendrik Lenstra in their article on "Algorithms in Number Theory". It was introduced in their analysis of a discrete logarithm algorithm of Coppersmith. This is the most commonly used form in the literature today.

The Handbook of Applied Cryptography defines the L-notation with a big O around the formula presented in this article. This is not the standard definition. The big O would suggest that the running time is an upper bound. However, for the integer factoring and discrete logarithm algorithms that L-notation is commonly used for, the running time is not an upper bound, so this definition is not preferred.

References

References

1. Hendrik W. Lenstra Jr. and Carl Pomerance, "Primality testing with Gaussian periods", preprint, 2011, http://www.math.dartmouth.edu/~carlp/aks041411.pdf.
2. Carl Pomerance, "Analysis and comparison of some integer factoring algorithms", In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982, http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf
3. Arjen K. Lenstra and Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.
4. Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. {{isbn. 0-8493-8523-7. http://www.cacr.math.uwaterloo.ca/hac/.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::