Notação L

A notação L é uma notação assintótica análoga à notação Big O (Grande O), denotada como ${\displaystyle L_{n}[\alpha ,c]}$ para uma variável limitada ${\displaystyle n}$ tendendo ao infinito. Assim como a notação Big O, ela é geralmente usada para transmitir de forma aproximada a taxa de crescimento de uma função, como a complexidade computacional de um algoritmo específico.

É definida como

${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$

onde c é uma constante positiva, e ${\displaystyle \alpha }$ é uma constante ${\displaystyle 0\leq \alpha \leq 1}$.

A notação L é usada principalmente na teoria dos números computacional, para expressar a complexidade de algoritmos para problemas difíceis da teoria dos números, por exemplo, crivos para fatoração de inteiros e métodos para resolver logaritmos discretos. O benefício desta notação é que ela simplifica a análise desses algoritmos. O termo ${\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ expressa o termo dominante, e o termo ${\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$ cuida de tudo o que é menor. Quando ${\displaystyle \alpha }$ é 0, então

${\displaystyle L_{n}[\alpha ,c]=L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,}$

é uma função polilogarítmica (uma função polinomial de ln n);

Quando ${\displaystyle \alpha }$ é 1, então

${\displaystyle L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}\,}$

é uma função exponencial completa de ln n (e, portanto, polinomial em n).

Se ${\displaystyle \alpha }$ estiver entre 0 e 1, a função é subexponencial de ln n (e superpolinomial).

Muitos algoritmos de fatoração de inteiros de propósito geral têm complexidades de tempo subexponenciais. O melhor é o crivo de campo numérico geral, que tem um tempo de execução esperado de

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

para ${\displaystyle c=(64/9)^{1/3}\approx 1.923}$. O melhor algoritmo desse tipo antes do crivo de campo numérico era o crivo quadrático [en], que tem tempo de execução

${\displaystyle L_{n}[1/2,1]=e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}$

o terceiro método de fatoração mais rápido conhecido: fatoração por curva elíptica de Lenstra [en], que tem tempo de execução

${\displaystyle L_{n}[1/2,2^{1/2}]=e^{(2^{1/2}+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}$

Para o problema do logaritmo discreto de curva elíptica, o algoritmo de propósito geral mais rápido é o algoritmo passo de bebê, passo de gigante [en], que tem um tempo de execução da ordem da raiz quadrada da ordem do grupo n. Em notação L, isso seria

${\displaystyle 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 por ser no máximo

${\displaystyle L_{n}[0,c]=(\ln n)^{c+o(1)}\,}$

onde c foi provado ser no máximo 6.^[1]

A notação L foi definida em várias formas ao longo da literatura. O primeiro uso veio de Carl Pomerance em seu artigo "Analysis and comparison of some integer factoring algorithms".^[2] Esta forma tinha apenas o parâmetro ${\displaystyle c}$: o ${\displaystyle \alpha }$ na fórmula era ${\displaystyle 1/2}$ para os algoritmos que ele estava analisando. Pomerance vinha usando a letra ${\displaystyle L}$ (ou minúscula ${\displaystyle l}$) neste e em artigos anteriores para fórmulas que envolviam muitos logaritmos.

A fórmula acima, envolvendo dois parâmetros, foi introduzida por Arjen Lenstra [en] e Hendrik Lenstra em seu artigo sobre "Algorithms in Number Theory".^[3] Foi introduzida em sua análise de um algoritmo de logaritmo discreto de Don Coppersmith. Esta é a forma mais comumente usada na literatura hoje.

O Handbook of Applied Cryptography (Manual de Criptografia Aplicada) define a notação L com um Big O (${\displaystyle O}$) em torno da fórmula apresentada neste artigo.^[4] Esta não é a definição padrão. O Big O sugeriria que o tempo de execução é um limite superior. No entanto, para os algoritmos de fatoração de inteiros e logaritmo discreto para os quais a notação L é comumente usada, o tempo de execução não é um limite superior, então esta definição não é a preferida.