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\le \alpha \le 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.