# Notação L

​A notação L é uma notação assintótica análoga à notação O grande, denotada como $L_{n}[\alpha ,c]$ para uma variável limitada $n$ tendendo ao infinito. Como a notação O grande, geralmente é usada para transmitir aproximadamente a complexidade computacional de um algoritmo específico.

## Definição

Ela está definida como
    $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ onde c é uma constante positiva e $\alpha$ é uma constante $0\leq \alpha \leq 1$.
A notação L é usada principalmente na teoria computacional dos números, para expressar a complexidade de algoritmos para problemas difíceis da teoria dos números, por ex. peneiras para fatoração de inteiros e métodos para resolver logaritmos discretos. O benefício dessa notação é que ela simplifica a análise desses algoritmos.
$e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ expressa o termo dominante, e $e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ cuida de tudo menor.
Quando $\alpha$ ​0, então
    $L_{n}[\alpha ,c]=L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,$
é uma função polinomial de ln n;
Quando $\alpha$ é 1, então
    $L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}\,$
é uma função totalmente exponencial de ln n (e, portanto, polinomial em n).
Se $\alpha$ estiver entre 0 e 1, a função é subexponencial de ln n (e superpolinomial).

## Exemplos

Muitos algoritmos de fatoração de inteiros de propósito geral têm complexidades temporais subexponenciais. O melhor é a peneira de campo de número geral, que tem um tempo de execução esperado de
    $L_{n}[1/3,c]=e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}$
para $c=(64/9)^{1/3}\approx 1,923$. O melhor algoritmo antes da peneira de campo numérico era a peneira quadrática que tem tempo de execução
    $L_{n}[1/2,1]=e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,$
Para o problema de logaritmo discreto de curva elíptica, o algoritmo de propósito geral mais rápido é o algoritmo passo de bebê passo gigante, que tem um tempo de execução na ordem da raiz quadrada da ordem n. Em notação L, isso seria
    $L_{n}[1,1/2]=n^{1/2+o(1)}.\,$
A existência do teste de primalidade AKS, que é executado em tempo polinomial, significa que a complexidade de tempo para o teste de primalidade é conhecida como sendo no máximo
    $L_{n}[0,c]=(\ln n)^{c+o(1)}\,$
onde c foi provado ser no máximo 6.

## História

A notação L foi definida de várias formas na literatura. O primeiro uso dela veio de Carl Pomerance em seu artigo "Análise e comparação de alguns algoritmos de fatoração de inteiros". Esta forma tinha apenas o parâmetro $c$: o $\alpha$ na fórmula era $1/2$ para os algoritmos que ele estava analisando. Pomerance estava usando a letra $L$ (ou minúscula $l$) neste trabalho e em trabalhos anteriores para fórmulas que envolviam muitos logaritmos.
A fórmula acima envolvendo dois parâmetros foi introduzida por Arjen Lenstra e Hendrik Lenstra em seu artigo sobre "algoritmos na teoria dos números". Foi introduzido na análise de um algoritmo de logaritmo discreto de Coppersmith. Esta é a forma mais comumente usada na literatura hoje.
O manual de criptografia aplicada define a notação L com um $O$ grande em torno da fórmula apresentada neste artigo. Esta não é a definição padrão. O $O$ grande sugere que o tempo de execução é um limite superior. No entanto, para os algoritmos de fatoração de inteiros e logaritmos discretos para os quais a notação L é comumente usada, o tempo de execução não é um limite superior, portanto, essa definição não é preferida.