Notação L

Origem: Wikipédia, a enciclopédia livre.

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

Definição[editar | editar código-fonte]

Ela está definida como

onde c é uma constante positiva e é uma constante .

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.

expressa o termo dominante, e cuida de tudo menor.

Quando ​0, então

é uma função polinomial de ln n;

Quando é 1, então

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

Se estiver entre 0 e 1, a função é subexponencial de ln n (e superpolinomial).

Exemplos[editar | editar código-fonte]

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

para . O melhor algoritmo antes da peneira de campo numérico era a peneira quadrática que tem tempo de execução

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

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

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

História[editar | editar código-fonte]

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".[2] Esta forma tinha apenas o parâmetro : o na fórmula era para os algoritmos que ele estava analisando. Pomerance estava usando a letra (ou minúscula ) 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".[3] 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 grande em torno da fórmula apresentada neste artigo.[4] Esta não é a definição padrã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.

Referências[editar | editar código-fonte]

  1. Hendrik W. Lenstra Jr. e Carl Pomerance, "Teste de primalidade com períodos gaussianoss", preprint, 2011, http://www.math.dartmouth.edu/~carlp/aks041411.pdf.
  2. Carl Pomerance, "Análise e comparação de alguns algoritmos de fatoração inteira", em métodos computacionais na teoria dos números mathematisch centrum, parte 1, páginas 89 à 139, 1982, http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf (em inglês).
  3. Arjen K. Lenstra e Hendrik W. Lenstra, Jr, "Algoritmos na teoria dos números", no manual de ciência da computação teórica (volume A): Algoritmos e complexidade, 1991 (em inglês).
  4. Alfred J. Menezes, Paul C. van Oorschot e Scott A. Vanstone. Manual de criptografia aplicada. CRC Press, 1996. ISBN 0-8493-8523-7. http://www.cacr.math.uwaterloo.ca/hac/ (em inglês).