Notación L

Notación que describe el comportamiento limitante en la teoría de números computacional

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 . ${\displaystyle L_{n}[\alpha ,c]}$ ${\displaystyle n}$

Definició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 . ${\displaystyle \alpha }$ ${\displaystyle 0\leq \alpha \leq 1}$

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. ${\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 ${\displaystyle \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 ${\displaystyle \alpha }$

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

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 ). ${\displaystyle \alpha }$

Ejemplos

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

${\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 del tamiz de campos numéricos era el tamiz cuadrático que tiene tiempo de ejecución. ${\displaystyle c=(64/9)^{1/3}\approx 1.923}$

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

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

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

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

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

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

Historia

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. ${\displaystyle c}$ ${\displaystyle \alpha }$ ${\displaystyle 1/2}$ ${\displaystyle L}$ ${\displaystyle 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 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. ${\displaystyle O}$ ${\displaystyle O}$

Referencias

1. Hendrik W. Lenstra Jr. y Carl Pomerance, "Prueba de primalidad con períodos gaussianos", preimpresión, 2011, http://www.math.dartmouth.edu/~carlp/aks041411.pdf.
2. Carl Pomerance, "Análisis y comparación de algunos algoritmos de factorización de enteros", en Mathematisch Centrum Computational Methods in Number Theory, Parte 1, págs. 89-139, 1982, http://www.math.dartmouth.edu/~carlp/ PDF/comparación de análisis.pdf
3. Arjen K. Lenstra y Hendrik W. Lenstra, Jr, "Algoritmos en teoría de números", en Manual de informática teórica (vol. A): Algoritmos y complejidad, 1991.
4. Alfred J. Menezes, Paul C. van Oorschot y Scott A. Vanstone. Manual de criptografía aplicada. Prensa CRC, 1996. ISBN  0-8493-8523-7 . http://www.cacr.math.uwaterloo.ca/hac/.