La notación L es una notación asintótica análoga a la notación O grande , denotada comopara una variable ligada que tiende al infinito . Al igual que la notación O grande, generalmente se usa para transmitir de manera aproximada la tasa de crecimiento de una función , como la complejidad computacional de un algoritmo particular .
Se define como
donde c es una constante positiva y es una constante .
La notación L se utiliza principalmente en teoría computacional de números , para expresar la complejidad de los algoritmos para problemas difíciles de teoría de números , por ejemplo, tamices para factorización de números enteros y métodos para resolver logaritmos discretos . El beneficio de esta notación es que simplifica el análisis de estos algoritmos. El expresa el término dominante y el se ocupa de todo lo más pequeño.
Cuando es 0, entonces
es una función polilogarítmica (una función polinómica de ln n );
cuando es 1 entonces
es una función totalmente exponencial de ln n (y por tanto polinomio en n ).
Si está entre 0 y 1, la función es subexponencial de ln n (y superpolinomio ).
Muchos algoritmos de factorización de enteros de propósito general tienen complejidades de tiempo subexponenciales . El mejor es el tamiz de campo numérico general , que tiene un tiempo de funcionamiento esperado de
para . El mejor algoritmo de este tipo antes del tamiz de campos numéricos era el tamiz cuadrático que tiene tiempo de ejecución.
Para el problema de logaritmo discreto de curva elíptica , el algoritmo de propósito general más rápido es el algoritmo de paso gigante , que tiene un tiempo de ejecución del orden de la raíz cuadrada del orden del grupo n . En notación L esto sería
La existencia de la prueba de primalidad de AKS , que se ejecuta en tiempo polinomial , significa que se sabe que la complejidad temporal para las pruebas de primalidad es como máximo
donde se ha demostrado que c es como máximo 6. [1]
La notación L se ha definido de varias formas a lo largo de la literatura. El primer uso provino de Carl Pomerance en su artículo "Análisis y comparación de algunos algoritmos de factorización de enteros". [2] Este formulario tenía solo el parámetro: el de la fórmula era para los algoritmos que estaba analizando. Pomerance había estado usando la letra (o minúscula ) en este y en artículos anteriores para fórmulas que involucraban muchos logaritmos.
La fórmula anterior que involucra dos parámetros fue introducida por Arjen Lenstra y Hendrik Lenstra en su artículo sobre "Algoritmos en teoría de números". [3] Fue introducido en su análisis de un algoritmo de logaritmo discreto de Coppersmith . Esta es la forma más utilizada en la literatura actual.
El Manual de Criptografía Aplicada define la notación L con un gran alrededor de la fórmula presentada en este artículo. [4] Esta no es la definición estándar. Lo grande sugeriría que el tiempo de ejecución es un límite superior. Sin embargo, para los algoritmos de factorización de enteros y logaritmos discretos para los que se utiliza comúnmente la notación L, el tiempo de ejecución no es un límite superior, por lo que no se prefiere esta definición.