Notación L

La notación L es unanotación asintótica análoga a la notación O mayúscula , que se denota comopara una variable ligada que tiende al infinito . Al igual que la notación O mayúscula, se utiliza generalmente para expresar de forma aproximada la tasa de crecimiento de una función , como la complejidad computacional de un algoritmo en particular . ${\displaystyle L_{n}[\alpha,c]}$ ${\estilo de visualización n}$

Se define como

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

donde c es una constante positiva y es una constante . ${\estilo de visualización \alpha}$${\displaystyle 0\leq \alpha \leq 1}$

La notación L se utiliza principalmente en la teoría de números computacionales para expresar la complejidad de algoritmos para problemas difíciles de teoría de números , por ejemplo, cribas 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. La expresa el término dominante y la se ocupa de todo lo más pequeño. ${\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$${\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$

Cuando es 0, entonces ${\estilo de visualización \alpha}$

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

es una función polilogarítmica (una función polinómica de ln  n );

Cuando es 1 entonces ${\estilo de visualización \alpha}$

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

es una función completamente exponencial de ln  n (y por lo tanto polinómica en n ).

Si está entre 0 y 1, la función es subexponencial de ln  n (y superpolinomial ). ${\estilo de visualización \alpha}$

Muchos algoritmos de factorización de números enteros de propósito general tienen complejidades temporales subexponenciales . El mejor es el tamiz de campo numérico general , que tiene un tiempo de ejecución esperado de

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

para . El mejor algoritmo de este tipo antes de la criba de cuerpo numérico era la criba cuadrática , cuyo tiempo de ejecución ${\displaystyle c=(64/9)^{1/3}\aproximadamente 1,923}$

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

Para el problema del logaritmo discreto de la curva elíptica , el algoritmo de propósito general más rápido es el algoritmo de pasos pequeños y pasos gigantes , que tiene un tiempo de ejecución del orden de la raíz cuadrada del orden de grupo n . En notación L, esto sería

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

La existencia de la prueba de primalidad AKS , que se ejecuta en tiempo polinomial , significa que se sabe que la complejidad temporal para la prueba de primalidad es como máximo

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

donde se ha demostrado que c es como máximo 6. ^[1]

La notación L se ha definido en varias formas a lo largo de la literatura. El primer uso de la misma provino de Carl Pomerance en su artículo "Análisis y comparación de algunos algoritmos de factorización de números enteros". ^[2] Esta forma solo tenía el parámetro: el en 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. ${\estilo de visualización c}$${\estilo de visualización \alpha}$${\estilo de visualización 1/2}$${\estilo de visualización L}$${\estilo de visualización l}$

La fórmula anterior que involucra dos parámetros fue introducida por Arjen Lenstra y Hendrik Lenstra en su artículo sobre "Algoritmos en la teoría de números". ^[3] Fue introducida 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 una mayúscula en torno a la fórmula presentada en este artículo. ^[4] Esta no es la definición estándar. La mayúscula sugeriría que el tiempo de ejecución es un límite superior. Sin embargo, para los algoritmos de factorización de números 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 esta definición no es la preferida. ${\estilo de visualización O}$${\estilo de visualización O}$