El algoritmo de reducción de la base de celosía de Lenstra – Lenstra – Lovász (LLL) es un algoritmo de reducción de celosía 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 n ) con, el algoritmo LLL calcula una base de celosía reducida LLL (corta, casi ortogonal ) en el tiempo
dónde es la mayor longitud de bajo la norma euclidiana, es decir, . [2] [3]
Las aplicaciones originales eran proporcionar algoritmos de tiempo polinomial para factorizar polinomios con coeficientes racionales , encontrar aproximaciones racionales simultáneas a números reales y resolver el problema de programación lineal de enteros en dimensiones fijas.
Reducción de LLL
La definición precisa de LLL reducida es la siguiente: Dada una base
definir su base ortogonal del proceso de Gram-Schmidt
y los coeficientes de Gram-Schmidt
- , para cualquier .
Entonces la base se reduce LLL si existe un parámetro en (0.25,1] tal que se cumple lo siguiente:
- (tamaño reducido) Para . Por definición, esta propiedad garantiza la reducción de longitud de la base ordenada.
- (Condición de Lovász) Para k = 2,3, .., n .
Aquí, estimando el valor de la parámetro, podemos concluir qué tan bien se reduce la base. Mayores valores deconducir 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. Tenga en cuenta que aunque la reducción de LLL está bien definida para, la complejidad de tiempo polinomial está garantizada solo para en .
El algoritmo LLL calcula bases reducidas de LLL. No existe un algoritmo eficiente conocido para calcular una base en la que los vectores de base sean lo más cortos posible para celosías de dimensiones superiores a 4. [4] Sin embargo, una base LLL reducida es casi tan corta como sea posible, en el sentido de que hay son límites absolutos tal que el primer vector base no sea más que veces tan largo como un vector más corto en la red, el segundo vector base está igualmente dentro de del segundo mínimo sucesivo, y así sucesivamente.
Aplicaciones
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 muchas 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 de números enteros . 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 abarcado 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 tal vector es "corto" sólo si a , b , c son pequeños yes aún 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 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 ....
Propiedades de la base LLL reducida
Dejar ser un -LLL-base reducida de una celosía . A partir de la definición de base reducida de LLL, podemos derivar varias otras propiedades útiles sobre.
- El primer vector de la base no puede ser mucho más grande que el vector más corto distinto de cero :. En particular, para, esto da . [8]
- El primer vector de la base también está acotado por el determinante de la red: . En particular, para, esto da .
- El producto de las normas de los vectores en la base no puede ser mucho mayor que el determinante de la red: sea , luego .
Pseudocódigo del algoritmo LLL
La siguiente descripción se basa en ( Hoffstein, Pipher & Silverman 2008 , Teorema 6.68), con las correcciones de la errata. [9]
ENTRADA a base de celosía un parámetro con , más comúnmente PROCEDIMIENTO y no normalizar utilizando los valores más actuales de y tiempo hacer por de a hacer si luego Actualizar y el relacionado es según sea necesario. (El método ingenuo es volver a calcular cuando sea cambios: ) terminar si terminar para si luego más Swap y Actualizar y el relacionado es según sea necesario. termina si termina mientras regresa la LLL reduce la base de SALIDA la base reducida
Ejemplos de
Ejemplo de
Deje una base de celosía , estar dado por las columnas de
entonces la base reducida es
- ,
que tiene un tamaño reducido, satisface la condición de Lovász y, por lo tanto, está reducido por LLL, como se describió anteriormente. Véase W. Bosma. [10] para obtener detalles sobre el proceso de reducción.
Ejemplo de
Asimismo, para la base sobre los enteros complejos dados por las columnas de la matriz a continuación,
- ,
luego, las columnas de la matriz a continuación dan una base de LLL reducida.
- .
Implementaciones
LLL se implementa en
- Arageli como función
lll_reduction_int
- fpLLL como implementación independiente
- GAP como función
LLLReducedBasis
- Macaulay2 como función
LLL
en el paqueteLLLBases
- Magma como funciones
LLL
yLLLGram
(tomando una matriz de gramos) - Arce como función
IntegerRelations[LLL]
- Mathematica como función
LatticeReduce
- Biblioteca de teoría numérica (NTL) como función
LLL
- PARI / GP como función
qflll
- Pymatgen como función
analysis.get_lll_reduced_lattice
- SageMath como método
LLL
impulsado por fpLLL y NTL - Isabelle / HOL en la entrada 'Archivo de pruebas formales'
LLL_Basis_Reduction
. Este código se exporta a Haskell eficientemente ejecutable. [11]
Ver también
- Método de calderero
Notas
- ^ Lenstra, AK ; Lenstra, HW, Jr .; Lovász, L. (1982). "Factorizar polinomios con coeficientes racionales". Mathematische Annalen . 261 (4): 515–534. CiteSeerX 10.1.1.310.318 . doi : 10.1007 / BF01457454 . hdl : 1887/3810 . Señor 0682664 . S2CID 5701340 .
- ^ Galbraith, Steven (2012). "capítulo 17" . Matemáticas de la criptografía de clave pública .
- ^ 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 .
- ^ Nguyen, Phong Q .; Stehlé, Damien (1 de octubre de 2009). "Revisión de la reducción de la base de celosía de baja dimensión". Transacciones ACM sobre algoritmos . 5 (4): 1–48. doi : 10.1145 / 1597036.1597050 . S2CID 10583820 .
- ^ Odlyzko, Andrew; 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 .
- ^ Shahabuddin, Shahriar et al., "Un multiprocesador de reducción de celosía personalizado para la detección de MIMO", en la preimpresión de Arxiv, enero de 2015.
- ^ D. Simon (2007). "Aplicaciones seleccionadas de LLL en teoría de números" (PDF) . Conferencia LLL + 25 . Caen, Francia.
- ^ Regev, Oded. "Celosías en informática: algoritmo LLL" (PDF) . Universidad de Nueva York . Consultado el 1 de febrero de 2019 .
- ^ Silverman, Joseph. "Introducción a la errata de criptografía matemática" (PDF) . Departamento de Matemáticas de la Universidad de Brown . Consultado el 5 de mayo de 2015 .
- ^ Bosma, Wieb. "4. LLL" (PDF) . Apuntes de conferencias . Consultado el 28 de febrero de 2010 .
- ^ Divasón, José (2018). "Una formalización del algoritmo de reducción de base LLL" . Documento de conferencia . Apuntes de conferencias en Ciencias de la Computación. 10895 : 160-177. doi : 10.1007 / 978-3-319-94821-8_10 . ISBN 978-3-319-94820-1. Consultado el 3 de mayo de 2020 .
Referencias
- Napias, Huguette (1996). "Una generalización del algoritmo LLL sobre anillos u órdenes euclidianos" . Journal de Théorie des Nombres de Bordeaux . 8 (2): 387–396. doi : 10.5802 / jtnb.176 .
- Cohen, Henri (2000). Un curso de teoría de números algebraica computacional . GTM. 138 . Saltador. 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 . Saltador. ISBN 978-0-387-77993-5.