Notación L

L - notación es un asintótica análoga notación para notación de orden O , denotado comopara una variable ligada tendiendo a infinito . Al igual que la notación Big-O, generalmente se usa para transmitir aproximadamente la complejidad computacional de un algoritmo en 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 usa principalmente en la teoría de números computacional , para expresar la complejidad de algoritmos para problemas difíciles de teoría de números , por ejemplo, tamices para factorización de 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 encarga 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 polinomial 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 completamente exponencial de ln  n (y por lo tanto polinomial en n ).

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

Ejemplos

Muchos algoritmos de factorización de 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 del tamiz de campo numérico era el tamiz cuadrático que tiene tiempo de funcionamiento${\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 del logaritmo discreto de la curva elíptica , el algoritmo de propósito general más rápido es el algoritmo de paso de bebé paso gigante , que tiene un tiempo de ejecución del orden de la raíz cuadrada del orden de grupo n . En la 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 del tiempo 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]

Historia

La notación L se ha definido de diversas 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 enteros". ^[2] Este formulario 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.${\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 hoy.

El Manual de criptografía aplicada define la notación L con un gran círculo 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 entera y logaritmo discreto para los que se usa 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 primordialidad 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 / analysiscomparison.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. CRC Press, 1996. ISBN  0-8493-8523-7 . http://www.cacr.math.uwaterloo.ca/hac/ .