Notación L

La notación L es una notación asintótica similar ala notación O , escritacon tendencia a infinito . Al igual que Big O , la notación L se usa generalmente para aproximar la complejidad computacional de un algoritmo en particular . Al mismo tiemporepresenta algún parámetro de los datos de entrada del algoritmo, proporcional a su tamaño: por ejemplo, el número de vértices y aristas en el gráfico de entrada en algoritmos para encontrar el camino más corto en él, o un número natural en algoritmos para descomponerlo en factores simples . $L_{n}[\alfa,c]$ $norte$ $norte$

$L_{n}[\alfa,c]$ está determinada por la fórmula

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

donde es una constante positiva y es una constante . $C$ $\alfa$ ${\ estilo de visualización 0 \ leq \ alfa \ leq 1}$

La notación L se utiliza principalmente en la teoría computacional de números para expresar la complejidad de los algoritmos para problemas difíciles en la teoría de números , como algoritmos tamiz para factorizar números naturales en factores primos y métodos para calcular logaritmos discretos . La ventaja de esta notación es simplificar el análisis de algoritmos.

El factor en refleja el componente dominante, y el factor se refiere a todo lo menos significativo. Sin embargo, cuando es 0, $e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha ))$ $L_{n}[\alfa,c]$ $e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha ))$ $\alfa$

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

es un polinomio en ln n , mientras que cuando es igual a 1, $\alfa$

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

es un exponente de ln n (y por tanto un polinomio de n ). Si está entre 0 y 1, entonces la función es subexponencial , es decir, crece más lentamente que una función exponencial con una base mayor que 1 (o superpolinomio). $\alfa$ $L_{n}[\alfa,c]$

Ejemplos

Muchos algoritmos para descomponer números en factores primos tienen una complejidad temporal subexponencial. El mejor método en términos de ahorro de recursos computacionales es el método de criba de campo numérico general , que tiene la estimación:

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

para _ ${\ estilo de visualización c = (64/9) ^ {(1/3)))$

El mejor algoritmo, antes del desarrollo del tamiz de campos numéricos, era el método del tamiz cuadrático , que tiene una estimación de complejidad de:

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 una curva elíptica , el algoritmo de aplicación general más rápido es el algoritmo de pasos grandes y pequeños: el algoritmo de Shanks , que tiene un tiempo de ejecución asintomático estimado igual a la raíz cuadrada del orden del grupo n . En notación L , esto se escribe:

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

La existencia de una prueba de primalidad AKS , que se ejecuta en tiempo polinomial , significa que la complejidad de una prueba de primalidad debe ser como máximo

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

y se prueba que c no debe exceder de 6. [1]

Historia

$L$ La notación ha sido definida en la literatura de varias maneras. La notación - fue aplicada por primera vez por Karl Pomerans en su trabajo "Análisis y comparación de algunos algoritmos de factorización de enteros" [2] . $L$

Esta forma tenía sólo un parámetro , que era una constante en la fórmula . Los habitantes de Pomerania usaron una letra (o minúscula ) en este artículo y en el anterior para fórmulas que contienen muchos logaritmos. $C$ $\alfa$ $1/2$ $L$ $yo$

La fórmula anterior que contiene dos parámetros fue presentada por Arjen Lenstra y Hendrik Lenstra en su artículo "Algorithms in Number Theory" [3] , donde la notación se utilizó en el análisis del logaritmo discreto del algoritmo de Coppersmith . Actualmente, la notación es la más utilizada en la literatura.

El Manual de criptografía aplicada define la notación L como [4] :

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

Esta no es una definición estándar. asume que el tiempo de ejecución del agente que ejecuta el algoritmo está acotado desde arriba. Sin embargo, para la factorización de enteros y el logaritmo discreto , la notación utilizada para la evaluación no es un límite superior, por lo que dicha definición no es del todo correcta. $O$ $L$

Notas

↑ Hendirk W. Lenstra Jr. y Carl Pomerance, Pruebas de primalidad con períodos gaussianos Archivado el 25 de febrero de 2012 en Wayback Machine , preimpresión, 2011.
↑ Carl Pomerance, Análisis y comparación de algunos algoritmos de factorización de enteros Archivado el 4 de febrero de 2021 en Wayback Machine , en Mathematisch Centrum Computational Methods in Number Theory, Part 1, págs. 89-139, 1982.
↑ Arjen K. Lenstra y Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", en Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1990.
↑ Alfred J. Menezes, Paul C. van Oorschot y Scott A. Vanstone. Manual de criptografía aplicada Archivado el 7 de marzo de 2005 en Wayback Machine . Prensa CRC, 1996. ISBN 0-8493-8523-7 .