Algoritmo Lenstra-Lenstra-Lovas

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 19 de marzo de 2020; las comprobaciones requieren 3 ediciones .

El algoritmo Lenstra-Lenstra-Lovas ( LLL-algorithm , LLL-algorithm ) es un algoritmo de reducción de base reticular desarrollado por Arjen Lenstra , Hendrik Lenstra y Laszlo Lovas en 1982 [1] . En tiempo polinomial, el algoritmo transforma una base en una red (subgrupo ) en la base casi ortogonal más corta en la misma red. A partir de 2019, el algoritmo Lenstra-Lenstra-Lovas es uno de los más eficientes para calcular la base reducida en redes de alta dimensión . Es relevante principalmente en problemas que se reducen a encontrar el vector de red más corto. $\mathbb{R} ^{n}$

Historia

El algoritmo fue desarrollado por los matemáticos holandeses Arjen Lenstra y Hendrik Lenstra junto con el matemático húngaro Laszlo Lovas en 1982 [1] [2] .

El principal requisito previo para la creación del algoritmo LLL fue que el proceso de Gram-Schmidt solo funciona con vectores cuyos componentes son números reales . Para un espacio vectorial , el proceso de Gram-Schmidt permite transformar una base arbitraria en una ortonormal (“ideal”, a la que tiende el algoritmo LLL). Pero el proceso de Gram-Schmidt no garantiza que en la salida cada uno de los vectores sea una combinación lineal entera de la base original. Por lo tanto, el conjunto de vectores resultante puede no ser la base de la red original. Esto llevó a la necesidad de crear un algoritmo especial para trabajar con celosías [3] . $\mathbb{R} ^{n}$

Inicialmente, el algoritmo se utilizó para factorizar polinomios con coeficientes enteros , calcular aproximaciones diofánticas de números reales y resolver problemas de programación lineal en espacios de dimensión fija , y más tarde para criptoanálisis [4] [2] .

Reducción de base

Una red en el espacio euclidiano es un subgrupo del grupo generado por vectores linealmente independientes de , llamado base de la red. Cualquier vector de celosía se puede representar mediante una combinación lineal entera de vectores base [5] . La base de una red se define de forma ambigua: la figura muestra dos bases diferentes de la misma red. ${\ estilo de visualización (\ mathbb {R} ^ {n}, +)}$ $d$ $\mathbb{R} ^{n}$

La reducción de base consiste en llevar la base de la red a una forma especial que satisfaga ciertas propiedades. La base reducida debe ser, si es posible, la más corta entre todas las bases de la red y cercana a la ortogonal (lo que se expresa en el hecho de que los coeficientes finales de Gram-Schmidt no deben ser mayores que ) [3] . $1/2$

Sea como resultado de la transformación de la base mediante el proceso de Gram-Schmidt , se obtiene la base , con los coeficientes de Gram-Schmidt definidos como sigue: $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\puntos,\mathbf {b} _{d}\}$ $\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b } _{d}^{*}\}$

{\textstyle \mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf { b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}}

, para todos los que .

{\ estilo de visualización j, i}

1\leqslant j<i\leqslant d

Entonces, una base (ordenada) se denomina base reducida -LLL (donde el parámetro está en el intervalo ) si cumple las siguientes propiedades [3] : $\matemáticas {B}$ $\delta$ $\delta$ ${\estilo de texto (0.25,1]}$

Para todos los que . (condición de reducción) $yo, j$ $1\leqslant j<i\leqslant d\colon \left|\mu _{i,j}\right|\leqslant 0{,}5$
Para presas: . (Condición de Lova) ${\ estilo de visualización k = 1,2, \ puntos, d}$ $(\delta -\mu _{k,k-1}^{2})\|\mathbf {b} _{k-1}^{*}\|^{2}\leqslant \|\ matemáticasbf {b} _{k}^{*}\|^{2}$

Aquí está la norma del vector , es el producto escalar de vectores. ${\ estilo de visualización \|\ matemáticas {b} \|}$ $\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle$

Inicialmente, Lenstra, Lenstra y Lovas demostraron el funcionamiento del algoritmo para el parámetro en su artículo . Aunque el algoritmo sigue siendo correcto para , su operación en tiempo polinomial está garantizada solo para en el intervalo [1] . ${\estilo de texto \delta ={\frac {3}{4}}}$ $\ delta = 1$ $\delta$ ${\ estilo de visualización (0.25,1)}$

Propiedades de base reducida

Sea una base sobre la red reducida por el algoritmo LLL con el parámetro . Varias propiedades pueden derivarse de la definición de tal base . Sea la norma del vector de red más corto, entonces: $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\puntos,\mathbf {b} _{d}\}$ $\delta$ ${\ matemática L}$ $\matemáticas {B}$ ${\ estilo de visualización \ lambda _ {1} ({\ matemáticas {L}})}$

El vector de primera base no puede ser significativamente más largo que el vector distinto de cero más corto : ${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1))}\right)^{d-1}\cdot \lambda _{1}({\mathcal {L}})}$ . En particular, porque resulta [6] . ${\ estilo de visualización \ delta = 3/4}$ $\|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/2}\cdot \lambda _{1}({\mathcal {L)))$
El primer vector base está limitado por el determinante de la red : ${\textstyle \|\mathbf {b} _{1}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1))}\right)^{(d-1)/ 2}\cdot \det({\mathcal {L}})^{1/d}}$ . En particular, porque resulta [3] . ${\ estilo de visualización \ delta = 3/4}$ ${\displaystyle \|\mathbf {b} _{1}\|\leqslant 2^{(d-1)/4}\cdot (\det {\mathcal {L)))^{1/d))$
El producto de normas vectoriales no puede ser mucho mayor que el determinante de la red: ${\textstyle \prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant \left({\frac {2}{\sqrt {4\delta -1)) }\right)^{d(d-1)/2}\cdot \det({\mathcal {L)))}$ . En particular, para [3] . $\prod _{i=1}^{d}\|\mathbf {b} _{i}\|\leqslant 2^{d(d-1)/4}\cdot \det({\mathcal {L)))$ ${\ estilo de visualización \ delta = 3/4}$

La base transformada por el método LLL es casi la más corta posible, en el sentido de que existen límites absolutos tales que el primer vector base no es más largo que el vector de red más corto, de manera similar, el segundo vector base no es más largo que un factor del segundo, el vector de red más corto, y así sucesivamente (que se deriva directamente de la propiedad 1) [6] . $c_{i}>1$ $c_{1}$ $c_{2}$

Algoritmo

Entrada [7] :

base de celosía (consiste en vectores linealmente independientes),

{\displaystyle \mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\in \displaystyle \mathbb {R} ^{3))

parámetro c , con mayor frecuencia (la elección del parámetro depende de la tarea específica).

{\ estilo de visualización \ delta}

{\textstyle {\frac {1}{4}}<\delta <1}

{\estilo de texto \delta ={\frac {3}{4}}}

Secuencia de acciones [4] :

En primer lugar, se crea una copia de la base original, que se ortogonaliza de modo que durante el transcurso del algoritmo se compare la base actual con la copia resultante en cuanto a ortogonalidad ( ). $\mathbf {b}_{1}^{*},\mathbf {b}_{2}^{*},\dots,\mathbf {b}_{d}^{*}$
Si cualquier coeficiente de Gram-Schmidt (c ) es mayor en valor absoluto que , entonces la proyección de uno de los vectores de la base actual sobre el vector de una base ortogonalizada con un número diferente es más de la mitad . Esto significa que es necesario restar del vector el vector multiplicado por el redondeado (el redondeo es necesario, ya que el vector de la red sigue siendo el vector de la misma red solo cuando se multiplica por un número entero, lo que se deriva de su definición). Luego se hace más pequeño , ya que ahora la proyección sobre será menos de la mitad . Por lo tanto, se verifica el cumplimiento de la primera condición de la definición de una base LLL reducida. ${\ estilo de visualización \ vert \ mu _ {k, j} \ vert}$ ${\ estilo de visualización j<k}$ $0{,}5$ ${\ estilo de visualización \ mathbf {b} _ {k}}$ ${\ estilo de visualización \ mathbf {b} _ {j}^{*}}$ ${\ estilo de visualización \ mathbf {b} _ {j}^{*}}$ ${\ estilo de visualización \ mathbf {b} _ {k}}$ ${\mathbf {b}}_{j}$ ${\ estilo de visualización \ vert \ mu _ {k, j} \ vert}$ ${\ estilo de visualización \ vert \ mu _ {k, j} \ vert}$ $0{,}5$ ${\ estilo de visualización \ mathbf {b} _ {k}}$ ${\ estilo de visualización \ mathbf {b} _ {j}^{*}}$ ${\ estilo de visualización \ mathbf {b} _ {j}^{*}}$
Recalculado para . ${\ estilo de visualización \ mu _ {k, j}}$ ${\ estilo de visualización j<k}$
Para , se comprueba la 2ª condición, introducida por los autores del algoritmo como la definición de una base LLL-reducida [1] . Si no se cumple la condición, se intercambian los índices de los vectores marcados. Y se vuelve a comprobar la condición para el mismo vector (ya con un nuevo índice). ${\ estilo de visualización \ mathbf {b} _ {k}}$
Recalculado por y para $\mathbf {b}_{k}^{*},\mathbf {b}_{k-1}^{*},\langle \mathbf {b}_{k}^{*},\ mathbf {b} _{k}^{*}\rangle ,\langle \mathbf {b}_{k-1}^{*},\mathbf {b}_{k-1}^{*}\rangle$ ${\ estilo de visualización k> 1}$ ${\ estilo de visualización \ mu _ {k-1, j}, \ mu _ {k, j}}$ ${\ estilo de visualización j<k}$
Si queda alguna que sobrepase en valor absoluto (ya con otra ), entonces debemos volver al punto 2. ${\ estilo de visualización \ mu _ {k, j}}$ $0{,}5$ $k$
Cuando se verifican todas las condiciones y se realizan cambios, el algoritmo termina.

En el algoritmo : redondeo según las reglas de las matemáticas. El proceso del algoritmo, descrito en pseudocódigo [7] : ${\ estilo de visualización \ lpiso \ mu _ {k, j} \ rceil}$

orto

:=\mathrm {gramSchmidt} (\{\mathbf {b} _{1},\dots ,\mathbf {b} _{d}\})=\{\mathbf {b} _{1} ^{*},\puntos,\mathbf {b} _{d}^{*}\}

(realizar el proceso de Gram-Schmidt sin normalización); determinar ,

{\textstyle \mu _{k,j}:={\frac {\langle \mathbf {b} _{k},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b}_{j}^{*}\rangle }}}

siempre implicando los valores más actuales

\mathbf {b} _{k},\mathbf {b} _{j}^{*}

asignados hasta

k=2

el momento :

k\leqslant d

para j de a 0 : si , entonces :; Actualizar valorespara; condición final ; fin de ciclo ; if , then : else : intercambio y lugares; Actualizar valorespara; para; ; condición final ; fin de ciclo .

k-1

{\estilo de texto |\mu _{k,j}|>{\frac {1}{2))}

{\displaystyle \mathbf {b}_{k}=\mathbf {b}_{k}-\lfloor \mu_{k,j}\rceil \mathbf {b}_{j))

{\ estilo de visualización | \ mu _ {k, j} |}

{\ estilo de visualización j<k}

{\textstyle (\delta -\mu _{k,k-1}^{2})\|\mathbf {b} _{k-1}^{*}\|^{2}\leqslant \|\ matemáticasbf {b} _{k}^{*}\|^{2}}

k=k+1

{\ estilo de visualización \ mathbf {b} _ {k}}

{\ estilo de visualización \ mathbf {b} _ {k-1}}

\mathbf {b}_{k}^{*},\mathbf {b}_{k-1}^{*},\langle \mathbf {b}_{k}^{*},\ mathbf {b} _{k}^{*}\rangle ,\langle \mathbf {b}_{k-1}^{*},\mathbf {b}_{k-1}^{*}\rangle

k>1

{\ estilo de visualización \ mu _ {k-1, j}, \ mu _ {k, j}}

{\ estilo de visualización j<k}

{\ estilo de visualización k = \ máximo (k-1,1)}

Datos de salida: base reducida: . ${\displaystyle \mathbf {b}_{1},\mathbf {b}_{2},\puntos,\mathbf {b}_{d))$

Complejidad computacional

La entrada contiene una base de vectores dimensionales con . $norte$ $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\puntos,\mathbf {b} _{d}\}$ ${\ estilo de visualización \ d \ leqslant n}$

Si los vectores base consisten en componentes enteros, el algoritmo aproxima la base casi ortogonal más corta en tiempo polinomial , donde es la longitud máxima en la norma euclidiana , es decir, . El bucle principal del algoritmo LLL requiere iteraciones y funciona con números de longitud . Dado que los vectores de longitud se procesan en cada iteración , como resultado, el algoritmo requiere operaciones aritméticas. El uso de algoritmos ingenuos para la suma y multiplicación de números enteros da como resultado operaciones bit a bit [3] . $O(d^{5}n\log^{3}B)$ $B$ ${\mathbf {b}}_{i}$ $B=\max \left(\|\mathbf {b} _{1}\|_{2},\|\mathbf {b} _{2}\|_{2},..., \|\mathbf {b} _{d}\|_{2}\right)$ $O(d^{2}\log B)$ $O(d\log B)$ $d$ $norte$ $O(d^{3}n\log^{3}B)$ $O(d^{5}n\log^{3}B)$

En el caso de que la red tenga una base con componentes racionales, estos números racionales primero deben convertirse en números enteros multiplicando los vectores base por los denominadores de sus componentes (el conjunto de denominadores está limitado a algún número entero ). Pero entonces las operaciones ya se realizarán en números enteros que no excedan . Como resultado, habrá un máximo de operaciones de bits . Para el caso en que la red se da en , la complejidad del algoritmo sigue siendo la misma, pero aumenta el número de operaciones de bits. Dado que en la representación por computadora cualquier número real se reemplaza por uno racional debido a la limitación de la representación de bits, la estimación resultante también es válida para redes reales [3] . $X$ ${\ estilo de visualización X ^ {nd}}$ $O(d^{8}n^{4}\log^{3}X)$ $\mathbb{R} ^{n}$

Al mismo tiempo, para dimensiones inferiores a 4, el problema de la reducción de la base se resuelve de manera más eficiente mediante el algoritmo de Lagrange [8] .

Ejemplo

Un ejemplo dado por Wib Bosma [9] .

Deje que la base de la red (como un subgrupo ) esté dada por las columnas de la matriz: $\mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in \displaystyle \mathbb {Z} ^{3}$ ${\ estilo de visualización (\ mathbb {R} ^ {n}, +)}$

{\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}

En el transcurso del algoritmo, se obtiene lo siguiente:

Proceso de ortogonalización de Gram-Schmidt
1. ${\textstyle b_{1}^{*}=b_{1}={\begin{bmatriz}1\\1\\1\end{bmatriz)),B_{1}=\langle b_{1}^{ *},b_{1}^{*}\rango =3}$
2. ${\textstyle \mu _{2,1}={\frac {\langle b_{2},b_{1}^{*}\rangle }{B_{1))}={\frac {1}{3 }}\izquierda(<{\frac{1}{2}}\derecha)}$ , y $b_{2}^{*}=b_{2}-\mu _{2,1}b_{1}^{*}={\begin{bmatrix}{\frac {-4}{3} }\\{\frac {-1}{3}}\\{\frac {5}{3}}\end{bmatriz}}$ ${\textstyle B_{2}=\langle b_{2}^{*},b_{2}^{*}\rangle ={\frac {14}{3)).}$
3. ${\estilo de texto \mu _{3,1}={\frac {14}{3}}(>{\frac {1}{2}})}$ , por lo tanto y , entonces y $b_{3}^{*}={\begin{bmatrix}{\frac {-5}{3}}\\{\frac {1}{3}}\\{\frac {4}{ 3}}\end{bmatriz}}$ ${\textstyle \mu _{3,2}={\frac {\langle b_{3},b_{2}^{*}\rangle}{B_{2))}={\frac {13}{14 }}\izquierda(>{\frac{1}{2}}\derecha)}$ ${\textstyle b_{3}^{*}={\begin{bmatrix}{\frac {-6}{14}}\\{\frac {9}{14}}\\{\frac {-3} {14}}\end{bmatriz}}}$ ${\textstyle B_{3}={\frac{9}{14))}$
Para tenemos y , entonces vamos al siguiente paso. $k=2$ ${\ estilo de visualización \ mu _ {2,1} {\ frac {1} {2}}}$ $(\delta -\mu _{2,1}^{2})\|\mathbf {b} _{1}^{*}\|^{2}\leqslant \|\mathbf {b} _ {2}^{*}\|^{2}$
cuando tenemos: $k=3$
1. $\lpiso \mu _{3,2}\rceil =1$ significa ahora ${\textstyle b_{3}=b_{3}-1\cdot b_{2}={\begin{bmatrix}3\\5\\6\end{bmatrix}}-{\begin{bmatrix}-1\ \0\\2\end{bmatriz}}={\begin{bmatriz}4\\5\\4\end{bmatriz}}}$ ${\textstyle \mu _{3,2}={\frac {13}{14}}-1=-{\frac {1}{14}},\mu _{3,1}={\frac { 13}{3}}}$
2. $\lpiso \mu _{3,1}\rceil =4$ significa ahora ${\textstyle b_{3}=b_{3}-4\cdot b_{1}={\begin{bmatrix}4\\5\\4\end{bmatrix}}-{\begin{bmatrix}4\\ 4\\4\end{bmatriz}}={\begin{bmatriz}0\\1\\0\end{bmatriz}}}$ ${\estilo de texto \mu _{3,2}=-{\frac {1}{14)),\mu _{3,1}={\frac {1}{3))}$
3. $(\delta -\mu _{3,2}^{2})\|\mathbf {b} _{2}^{*}\|^{2}>\|\mathbf {b} _ {3}^{*}\|^{2}$ , por lo que cambian de lugar. ${\ estilo de visualización b_ {3}}$ ${\ estilo de visualización b_ {2}}$
Ahora volvemos al paso 1, mientras que la matriz intermedia tiene la forma ${\ estilo de visualización (\ mathbf {b} _ {1}, \ mathbf {b} _ {2}, \ mathbf {b} _ {3})}$ ${\begin{bmatrix}1&0&-1\\1&1&0\\1&0&2\end{bmatrix}}$

Datos de salida: base reducida por el método Lenstra-Lenstra-Lovas:

{\begin{bmatrix}0&1&-1\\1&0&0\\0&1&2\end{bmatrix}}

Aplicación

El algoritmo se usa a menudo dentro del método MIMO (codificación de señal espacial) para decodificar señales recibidas por múltiples antenas [10] , y en criptosistemas de clave pública : criptosistemas basados en el problema de la mochila , RSA con configuraciones específicas, NTRUEncrypt , etc. . El algoritmo se puede utilizar para encontrar soluciones enteras en varios problemas de teoría de números, en particular, para encontrar las raíces de un polinomio en números enteros [11] .

En el proceso de ataques a criptosistemas de clave pública ( NTRU ), el algoritmo se utiliza para encontrar el vector de red más corto, ya que el algoritmo finalmente encuentra un conjunto completo de vectores más cortos [12] .

En el criptoanálisis RSA con un exponente CRT pequeño , la tarea, como en el caso de NTRU, se reduce a encontrar el vector de base reticular más corto que se encuentra en tiempo polinomial (desde la dimensión base) [13] .

En problemas de mochila, en particular, para atacar el criptosistema Merkle-Hellman, el algoritmo LLL busca una base de red reducida [14] .

Variaciones y generalizaciones

El uso de aritmética de punto flotante en lugar de una representación exacta de números racionales puede acelerar significativamente el algoritmo LLL a costa de errores numéricos muy pequeños [15] .

Implementaciones del algoritmo

Programáticamente, el algoritmo se implementa en el siguiente software:

En fpLLL como implementación independiente [16] ;
En GAP como función LLLReducedBasis [17] ;
En Macaulay2 como una función LLLen la biblioteca LLLBases [18] ;
En Magma ambas funciones LLLy LLLGram [19] ;
En Maple como función IntegerRelations[LLL] [20] ;
En Mathematica como una función LatticeReduce [21] ;
En la Biblioteca de Teoría de Números (NTL) como módulo LLL [22] ;
En PARI/GP como función qflll [23] ;
En Pymatgen como función analysis.get_lll_reduced_lattice [24] ;
En SageMath como método LLLimplementado en fpLLL y NTL [25] .

Notas

↑ 1 2 3 4 AK Lenstra, H. W. Lenstra Jr., L. Lovász. Factorización de polinomios con coeficientes racionales // Mathematische Annalen . - 1982. - S. 515-534 . — ISSN 4 . -doi : 10.1007/ BF01457454 .
↑ 1 2 El algoritmo LLL, 2010 , 1 La historia del algoritmo LLL.
↑ 1 2 3 4 5 6 7 Galbraith, Steven. 17. Reducción de celosía // Matemáticas de criptografía de clave pública (inglés) . - 2012. Archivado el 20 de septiembre de 2015 en Wayback Machine .
↑ 1 2 Xinyue, Deng. Introducción al algoritmo LLL // Instituto de Tecnología de Massachusetts. - Pág. 9-10 . Archivado desde el original el 8 de diciembre de 2019.
↑ Cherednik I. V. Base de celosía no negativa // 3.ª ed. — Discreto. Mat., 2014. - T. 26 . - S. 127-135 . (Ruso)
↑ 1 2 Regev, Oded. Lattices en Ciencias de la Computación: Algoritmo LLL // Universidad de Nueva York. Archivado desde el original el 20 de marzo de 2021.
↑ 1 2 Hoffstein, Jeffrey; Pipher, Jill; Silverman , JH Introducción a la criptografía matemática . — Springer, 2008. - Pág. 411. - ISBN 978-0-387-77993-5 .
↑ Nguyen, Phong Q., Stehlé, Damien. Revisión de la reducción de la base de celosía de baja dimensión // Transacciones ACM en algoritmos. — Pág. 1–48 . -doi : 10.1145/ 1597036.1597050 .
↑ Bosma, Wieb. 4. LLL // Álgebra informática. - 2007. Archivado el 8 de mayo de 2019.
↑ Shahriar Shahabuddin, Janne Janhunen, Zaheer Khan, Markku Juntti, Amanullah Ghazi. Un multiprocesador de reducción de celosía personalizado para detección MIMO // Simposio internacional IEEE sobre circuitos y sistemas (ISCAS) de 2015. - 2015. - arXiv : 1501.04860 . -doi : 10.1109 / ISCAS.2015.7169312 .
↑ D. Simón. Aplicaciones seleccionadas de LLL en teoría de números // Conferencia LLL+25. — Caen, Francia. Archivado el 6 de mayo de 2021.
↑ Abderrahmane, Nitaj. Criptoanálisis de NTRU con dos claves públicas // Asociación Internacional para la Investigación Criptológica. — Caen, Francia. Archivado desde el original el 21 de diciembre de 2019.
↑ Bleichenbacher, Daniel y May, Alexander. Nuevos ataques a RSA con pequeños exponentes CRT secretos // Asociación internacional para la investigación criptológica. — Darmstadt, Alemania. Archivado desde el original el 24 de junio de 2021.
↑ Liu, Jiayang, Bi, Jingguo y Xu, Songyan. Un ataque mejorado a los criptosistemas básicos Merkle-Hellman Knapsack // IEEE. — Pekín 100084, China. Archivado desde el original el 17 de junio de 2021.
↑ El algoritmo LLL, 2010 , 4 Progreso en LLL y Reducción de celosía.
↑ El equipo de desarrollo de la FPLLL. FPLLL, una biblioteca de reducción de celosía . — 2016. Archivado el 17 de febrero de 2020.
↑ Matrices integrales y celosías . GAP . Consultado el 10 de diciembre de 2019. Archivado desde el original el 19 de diciembre de 2019. (indefinido)
↑ LLLBases -- reducción de celosía (bases de Lenstra-Lenstra-Lovasz) . Macaulay2 . Consultado el 10 de diciembre de 2019. Archivado desde el original el 10 de diciembre de 2019. (indefinido)
↑ Reducción de LLL . magma _ Consultado el 10 de diciembre de 2019. Archivado desde el original el 10 de diciembre de 2019. (indefinido)
↑ Relaciones enteras/LLL . arce _ Consultado el 10 de diciembre de 2019. Archivado desde el original el 18 de septiembre de 2020. (indefinido)
↑ LatticeReduce . Documentación de Wolfram Language . Consultado el 10 de diciembre de 2019. Archivado desde el original el 10 de diciembre de 2019. (indefinido)
↑ MÓDULO: LLL . NTL . Consultado el 10 de diciembre de 2019. Archivado desde el original el 17 de agosto de 2018. (indefinido)
↑ Vectores, matrices, álgebra lineal y conjuntos . PARI/GP . Consultado el 10 de diciembre de 2019. Archivado desde el original el 18 de diciembre de 2019. (indefinido)
↑ módulo pymatgen.core.lattice . pymatgen _ Consultado el 27 de diciembre de 2019. Archivado desde el original el 18 de diciembre de 2019. (indefinido)
↑ Matrices densas sobre el anillo de enteros . sabio _ Consultado el 18 de diciembre de 2019. Archivado desde el original el 6 de mayo de 2021. (indefinido)

Literatura

Huguette, Napias. Una generalización del algoritmo LLL sobre anillos u órdenes euclidianos // J. The. Nombr. Burdeos. - 1996. - doi : 10.5802/jtnb.176 .
Cohen, Enrique. Un curso de teoría de números algebraicos computacionales (inglés) . — Springer, 2000. - vol. 138.- (GTM). — ISBN 3-540-55640-0 .
Borwein, Peter. Excursiones Computacionales en Análisis y Teoría de Números . - 2002. - ISBN 0-387-95444-9 .
Hoffstein, Jeffrey; Pipher, Jill; Silverman , JH Introducción a la criptografía matemática . — Springer, 2008. - ISBN 978-0-387-77993-5 .
Luk, Franklin T.; Qiao, Sanzheng. Un algoritmo LLL pivotado // Lin. Alg. Apli.. - 2011. - T. 434 , N º 11 . - S. 2296-2307 . -doi : 10.1016 / j.laa.2010.04.003 .
El Algoritmo LLL: Encuesta y Aplicaciones / Ed. por Phong Q. Nguyen y Brigitte Vallee. - Springer, 2010. - ISBN 978-3-642-02295-1 . -doi : 10.1007 / 978-3-642-02295-1 .
Murray R. Bremner. Reducción de la base de celosía: una introducción al algoritmo LLL y sus aplicaciones. - CRC Press, 2011. - ISBN 9781439807026 .

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin