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

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

Las aplicaciones originales tenían como objetivo 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.

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

Entonces la base${\displaystyle B}$se reduce LLL si existe un parámetro${\displaystyle \delta }$en (0.25, 1 ] de tal manera que se cumpla lo siguiente:

1. (tamaño reducido) Para${\displaystyle 1\leq j<i\leq n}$, tenemos${\displaystyle \left|\mu _{i,j}\right|\leq 0.5}$Por definición, esta propiedad garantiza la reducción de la longitud de la base ordenada.
2. (Condición de Lovász) Para${\displaystyle 2\leq k\leq n}$, tenemos${\displaystyle \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 de la${\displaystyle \delta }$parámetro, podemos concluir qué tan bien se reduce la base. Valores mayores de${\displaystyle \delta }$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${\displaystyle \delta =3/4}$. Tenga en cuenta que, si bien la reducción de LLL está bien definida para${\displaystyle \delta =1}$, la complejidad de tiempo polinomial está garantizada solo para${\displaystyle \delta }$en${\displaystyle (0.25,1)}$.

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

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

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

En particular, el algoritmo LLL constituye el 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${\displaystyle \mathbf {R} ^{4}}$abarcado por${\displaystyle [1,0,0,10000r^{2}],[0,1,0,10000r],}$y${\displaystyle [0,0,1,10000]}$. El primer vector en la base reducida será una combinación lineal entera de estos tres, por lo tanto necesariamente de la forma${\displaystyle [a,b,c,10000(ar^{2}+br+c)]}$; pero dicho vector es "corto" solo si a , b , c son pequeños y${\displaystyle ar^{2}+br+c}$es incluso más pequeño. Por lo tanto, es probable que las tres primeras entradas de este vector corto sean los coeficientes del polinomio cuadrático integral que tiene a 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,${\displaystyle x^{2}-x-1}$tiene una raíz igual a la proporción áurea , 1,6180339887....

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

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

La siguiente descripción se basa en ( Hoffstein, Pipher y Silverman 2008 , Teorema 6.68) , con las correcciones de las erratas. ^{[ 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 normalizar μ 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 hacer para j desde k −1 hasta 1 hacer si | μ k , j | > 1/2 entonces b k <- b k − ⌊ μ k , j ⌉ b j ; Actualizar B * y el μ i , j relacionado's según sea necesario. (El método ingenuo es recalcular B * cada vez que b i cambia: 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 ; Actualizar B * y los μ i , j relacionados's según sea necesario. k <- max( k −1, 2); fin si fin mientras devolver B la base reducida LLL de {b 1 , ..., b n } SALIDA la base reducida b 1 , b 2 , ..., b n en Z m

LLL se implementa en

• Arageli como funciónlll_reduction_int
• fpLLL como implementación independiente
• FLINT como funciónfmpz_lll
• GAP como funciónLLLReducedBasis
• Macaulay2 como la función LLLen el paqueteLLLBases
• Magma como las funciones LLLy LLLGram(tomando una matriz gram)
• Maple como funciónIntegerRelations[LLL]
• Mathematica como la funciónLatticeReduce
• Biblioteca de Teoría de Números (NTL) como la funciónLLL
• PARI/GP como funciónqflll
• Pymatgen como la 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 ejecutable de manera eficiente. ^{[ 11 ]}

• Método del herrero

• 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 . Springer. 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.