Algoritmo de reducción de base reticular Lenstra-Lenstra-Lovász

Algoritmo en la teoría de números computacionales

El algoritmo de reducción de base reticular de Lenstra–Lenstra–Lovász ( LLL ) es un algoritmo de reducción reticular de tiempo polinomial inventado por Arjen Lenstra , Hendrik Lenstra y László Lovász en 1982. ^[1] Dada una base con coordenadas enteras n -dimensionales, para una red L (un subgrupo discreto de R ⁿ ) con , el algoritmo LLL calcula una base reticular reducida por LLL (corta, casi ortogonal ) en el tiempo donde es la longitud más grande de bajo la norma euclidiana , es decir, . ^{[2] [3]} ${\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}}$ ${\displaystyle d\leq n}$ $${\displaystyle {\mathcal {O}}(d^{5}n\log ^{3}B)}$$ ${\displaystyle B}$ ${\displaystyle \mathbf {b} _{i}}$ ${\displaystyle B=\max \left(\|\mathbf {b} _{1}\|_{2},\|\mathbf {b} _{2}\|_{2},\dots ,\|\mathbf {b} _{d}\|_{2}\right)}$

Las aplicaciones originales fueron proporcionar algoritmos de tiempo polinomial para factorizar polinomios con coeficientes racionales , para encontrar aproximaciones racionales simultáneas a números reales y para resolver el problema de programación lineal entera en dimensiones fijas.

Reducción de LLL

La definición precisa de LLL-reducido es la siguiente: Dada una base , defina su base ortogonal del proceso de Gram-Schmidt y los coeficientes de Gram-Schmidt para cualquier . $${\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\},}$$ $${\displaystyle \mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\mathbf {b} _{2}^{*},\dots ,\mathbf {b} _{n}^{*}\},}$$ $${\displaystyle \mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }},}$$ ${\displaystyle 1\leq j<i\leq n}$

Entonces la base es LLL-reducida si existe un parámetro en (0.25, 1] ​​tal que se cumple lo siguiente: ${\displaystyle B}$ ${\displaystyle \delta }$

1. (tamaño reducido) Para . Por definición, esta propiedad garantiza la reducción de longitud de la base ordenada. ${\displaystyle 1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq 0.5}$
2. (Condición de Lovász) Para k = 2,3,...,n . ${\displaystyle \colon \delta \Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}\leq \Vert \mathbf {b} _{k}^{*}\Vert ^{2}+\mu _{k,k-1}^{2}\Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}}$

Aquí, estimando el valor del parámetro, podemos concluir qué tan bien se reduce la base. Valores mayores de conducen a reducciones más fuertes de la base. Inicialmente, A. Lenstra, H. Lenstra y L. Lovász demostraron el algoritmo de reducción LLL para . Nótese que aunque la reducción LLL está bien definida para , la complejidad de tiempo polinomial está garantizada solo para en . ${\displaystyle \delta }$ ${\displaystyle \delta }$ ${\displaystyle \delta ={\frac {3}{4}}}$ ${\displaystyle \delta =1}$ ${\displaystyle \delta }$ ${\displaystyle (0.25,1)}$

El algoritmo LLL calcula bases reducidas por LLL. No se conoce ningún algoritmo eficiente para calcular una base en la que los vectores de base sean lo más cortos posible para redes de dimensiones mayores que 4. ^[4] Sin embargo, una base reducida por LLL es casi lo más corta posible, en el sentido de que existen límites absolutos tales que el primer vector de base no es más de 100 veces más largo que un vector más corto en la red, el segundo vector de base está igualmente dentro del segundo mínimo sucesivo, y así sucesivamente. ${\displaystyle c_{i}>1}$ ${\displaystyle c_{1}}$ ${\displaystyle c_{2}}$

Aplicaciones

Una de las primeras aplicaciones exitosas del algoritmo LLL fue su uso por parte de Andrew Odlyzko y Herman te Riele para refutar la conjetura de Mertens . ^[5]

El algoritmo LLL ha encontrado numerosas otras aplicaciones en algoritmos de detección MIMO ^[6] y criptoanálisis de esquemas de cifrado de clave pública : criptosistemas de mochila , RSA con configuraciones particulares, NTRUEncrypt , etc. El algoritmo se puede utilizar para encontrar soluciones enteras a muchos problemas. ^[7]

En particular, el algoritmo LLL forma un núcleo de uno de los algoritmos de relación entera . Por ejemplo, si se cree que r = 1,618034 es una raíz (ligeramente redondeada) de una ecuación cuadrática desconocida con coeficientes enteros, se puede aplicar la reducción LLL a la red en la que se genera por y . El primer vector en la base reducida será una combinación lineal entera de estos tres, por lo tanto necesariamente de la forma ; pero un vector de este tipo es "corto" solo si a , b , c son pequeños y es incluso más pequeño. Por lo tanto, es probable que las primeras tres entradas de este vector corto sean los coeficientes del polinomio cuadrático integral que tiene r como raíz. En este ejemplo, el algoritmo LLL encuentra que el vector más corto es [1, -1, -1, 0,00025] y, de hecho, tiene una raíz igual a la proporción áurea , 1,6180339887.... ${\displaystyle \mathbf {R} ^{4}}$ ${\displaystyle [1,0,0,10000r^{2}],[0,1,0,10000r],}$ ${\displaystyle [0,0,1,10000]}$ ${\displaystyle [a,b,c,10000(ar^{2}+br+c)]}$ ${\displaystyle ar^{2}+br+c}$ ${\displaystyle x^{2}-x-1}$

Propiedades de la base reducida LLL

Sea una base -LLL-reducida de un retículo . A partir de la definición de base LLL-reducida, podemos derivar otras propiedades útiles sobre . ${\displaystyle \mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{n}\}}$ ${\displaystyle \delta }$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle \mathbf {B} }$

1. El primer vector en la base no puede ser mucho mayor que el vector no nulo más corto : . En particular, para , esto da . ^[8] ${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq (2/({\sqrt {4\delta -1}}))^{n-1}\cdot \lambda _{1}({\mathcal {L}})}$ ${\displaystyle \delta =3/4}$ ${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq 2^{(n-1)/2}\cdot \lambda _{1}({\mathcal {L}})}$
2. El primer vector en la base también está acotado por el determinante de la red: . En particular, para , esto da . ${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq (2/({\sqrt {4\delta -1}}))^{(n-1)/2}\cdot (\det({\mathcal {L}}))^{1/n}}$ ${\displaystyle \delta =3/4}$ ${\displaystyle \Vert \mathbf {b} _{1}\Vert \leq 2^{(n-1)/4}\cdot (\det({\mathcal {L}}))^{1/n}}$
3. El producto de las normas de los vectores en la base no puede ser mucho mayor que el determinante de la red: sea , entonces . ${\displaystyle \delta =3/4}$ ${\textstyle \prod _{i=1}^{n}\Vert \mathbf {b} _{i}\Vert \leq 2^{n(n-1)/4}\cdot \det({\mathcal {L}})}$

Pseudocódigo del algoritmo LLL

La siguiente descripción se basa en (Hoffstein, Pipher y Silverman 2008, Teorema 6.68), con las correcciones de la errata. ^[9]

ENTRADA una base reticular b 1 , b 2 , ..., b n en Z m un parámetro δ con 1/4 < δ < 1, más comúnmente δ = 3/4 PROCEDIMIENTO  B * <- GramSchmidt({ b 1 , ..., b n }) = { b 1 * , ..., b n * }; y no normalice  μ i , j <- InnerProduct( b i , b j * )/InnerProduct( b j * , b j * ); usando los valores más actuales de  b i y b j *  k <- 2; mientras  k <= n  haga  para  j  de  k −1 a 1 haga  si | μ k , j | > 1/2 entonces  b k <- b k − ⌊ μ k , j ⌉ b j ; Actualice  B *  y los μ i , j relacionados  según sea necesario. (El método ingenuo es volver a calcular B * siempre que b i cambie: B * <- GramSchmidt({ b 1 , ..., b n }) = { b 1 * , ..., b n * }) fin si fin para si InnerProduct( b k * , b k * ) > ( δ − μ 2 k , k −1 ) InnerProduct( b k −1 * , b k −1 * ) entonces k <- k + 1; de lo contrario, intercambiar b k y b k −1         ; Actualice  B *  y los  μ i , j relacionados según sea necesario.  k <- max( k −1, 2); fin si  fin mientras  devuelve  B la base reducida LLL de {b 1 , ..., b n } SALIDA la base reducida b 1 , b 2 , ..., b n en Z m

Ejemplos

Ejemplo de Z3

Sea una base reticular , dada por las columnas de entonces la base reducida es que es de tamaño reducido, satisface la condición de Lovász y, por lo tanto, es LLL-reducida, como se describió anteriormente. Véase W. Bosma. ^[10] para obtener detalles del proceso de reducción. ${\displaystyle \mathbf {b} _{1},\mathbf {b} _{2},\mathbf {b} _{3}\in \mathbf {Z} ^{3}}$ $${\displaystyle {\begin{bmatrix}1&-1&3\\1&0&5\\1&2&6\end{bmatrix}}}$$ $${\displaystyle {\begin{bmatrix}0&1&-1\\1&0&0\\0&1&2\end{bmatrix}},}$$

Ejemplo de Z[i]4

De la misma manera, para la base sobre los números enteros complejos dados por las columnas de la matriz siguiente, entonces las columnas de la matriz siguiente dan una base LLL reducida. $${\displaystyle {\begin{bmatrix}-2+2i&7+3i&7+3i&-5+4i\\3+3i&-2+4i&6+2i&-1+4i\\2+2i&-8+0i&-9+1i&-7+5i\\8+2i&-9+0i&6+3i&-4+4i\end{bmatrix}},}$$ $${\displaystyle {\begin{bmatrix}-6+3i&-2+2i&2-2i&-3+6i\\6-1i&3+3i&5-5i&2+1i\\2-2i&2+2i&-3-1i&-5+3i\\-2+1i&8+2i&7+1i&-2-4i\\\end{bmatrix}}.}$$

Implementaciones

LLL se implementa en

• Arageli como funciónlll_reduction_int
• fpLLL como una implementación independiente
• FLINT como funciónfmpz_lll
• GAP como funciónLLLReducedBasis
• Macaulay2 como función LLLen el paqueteLLLBases
• Magma como funciones LLLy LLLGram(tomando una matriz de gramo)
• El arce como funciónIntegerRelations[LLL]
• Mathematica como funciónLatticeReduce
• Biblioteca de teoría de números (NTL) como funciónLLL
• PARI/GP como funciónqflll
• Pymatgen como funciónanalysis.get_lll_reduced_lattice
• SageMath como método LLLimpulsado por fpLLL y ​​NTL
• Isabelle/HOL en la entrada 'Archivo de pruebas formales' LLL_Basis_Reduction. Este código se exporta a Haskell, que se ejecuta de manera eficiente. ^[11]

Véase también

• Método del calderero

Notas

1. Lenstra, Alaska ; Lenstra, HW Jr .; Lovász, L. (1982). "Factorización de polinomios con coeficientes racionales". Annalen Matemáticas . 261 (4): 515–534. CiteSeerX  10.1.1.310.318 . doi :10.1007/BF01457454. hdl : 1887/3810. SEÑOR  0682664. S2CID  5701340.
2. Galbraith, Steven (2012). "Capítulo 17". Matemáticas de la criptografía de clave pública .
3. Nguyen, Phong Q.; Stehlè, Damien (septiembre de 2009). "Un algoritmo LLL con complejidad cuadrática". SIAM J. Comput . 39 (3): 874–903. doi :10.1137/070705702 . Consultado el 3 de junio de 2019 .
4. Nguyen, Phong Q.; Stehlé, Damien (1 de octubre de 2009). "Revisión de la reducción de la base reticular de baja dimensión". ACM Transactions on Algorithms . 5 (4): 1–48. doi :10.1145/1597036.1597050. S2CID  10583820.
5. Odlyzko, Andrés; te Reile, Herman JJ "Refutando la conjetura de Mertens" (PDF) . Journal für die reine und angewandte Mathematik . 357 : 138-160. doi :10.1515/crll.1985.357.138. S2CID  13016831 . Consultado el 27 de enero de 2020 .
6. D. Wübben et al., "Reducción de red", IEEE Signal Processing Magazine, vol. 28, n.º 3, págs. 70-91, abril de 2011.
7. D. Simon (2007). "Aplicaciones seleccionadas de LLL en teoría de números" (PDF) . Conferencia LLL+25 . Caen, Francia.
8. Regev, Oded. "Lattices in Computer Science: LLL Algorithm" (PDF) . Universidad de Nueva York . Consultado el 1 de febrero de 2019 .
9. Silverman, Joseph. "Introducción a la criptografía matemática Errata" (PDF) . Departamento de Matemáticas de la Universidad de Brown . Consultado el 5 de mayo de 2015 .
10. Bosma, Wieb. "4.LLL" (PDF) . Apuntes de conferencias . Consultado el 28 de febrero de 2010 .
11. Divasón, Jose (2018). "Una formalización del algoritmo de reducción de base LLL". Documento de conferencia . Lecture Notes in Computer Science. 10895 : 160–177. doi : 10.1007/978-3-319-94821-8_10 . ISBN 978-3-319-94820-1.

Referencias

• Napias, Huguette (1996). "Una generalización del algoritmo LLL sobre anillos u órdenes euclidianos". Journal de Théorie des Nombres de Burdeos . 8 (2): 387–396. doi : 10.5802/jtnb.176 .
• Cohen, Henri (2000). Un curso de teoría algebraica computacional de números . GTM. Vol. 138. Springer. ISBN 3-540-55640-0.
• Borwein, Peter (2002). Excursiones computacionales en análisis y teoría de números . ISBN 0-387-95444-9.
• Luk, Franklin T.; Qiao, Sanzheng (2011). "Un algoritmo LLL pivotado". Álgebra lineal y sus aplicaciones . 434 (11): 2296–2307. doi : 10.1016/j.laa.2010.04.003 .
• Hoffstein, Jeffrey; Pipher, Jill; Silverman, JH (2008). Introducción a la criptografía matemática . Springer. ISBN 978-0-387-77993-5.