Reducción de celosía

Reducción de la red en dos dimensiones: los vectores negros son la base dada para la red (representada por puntos azules), los vectores rojos son la base reducida

En matemáticas, el objetivo de la reducción de la base de la red es encontrar una base con vectores cortos, casi ortogonales, cuando se le da una base de red entera como entrada. Esto se realiza mediante diferentes algoritmos, cuyo tiempo de ejecución suele ser al menos exponencial en la dimensión de la red.

Casi ortogonal

Una medida de casi ortogonalidad es el defecto de ortogonalidad . Esto compara el producto de las longitudes de los vectores base con el volumen del paralelepípedo que definen. Para vectores de base perfectamente ortogonales, estas cantidades serían las mismas.

Cualquier base particular de vectores puede representarse mediante una matriz , cuyas columnas son los vectores base . En el caso totalmente dimensional donde el número de vectores base es igual a la dimensión del espacio que ocupan, esta matriz es cuadrada, y el volumen del paralelepípedo fundamental es simplemente el valor absoluto del determinante de esta matriz . Si el número de vectores es menor que la dimensión del espacio subyacente, entonces el volumen es . Para una red dada , este volumen es el mismo (hasta el signo) para cualquier base y, por lo tanto, se le conoce como determinante de la red o constante de red . ${\displaystyle n}$ ${\displaystyle B}$ ${\displaystyle b_{i},i=1,\ldots ,n}$ ${\displaystyle \det(B)}$ ${\displaystyle {\sqrt {\det(B^{T}B)}}}$ ${\displaystyle \Lambda }$ ${\displaystyle \det(\Lambda )}$ ${\displaystyle d(\Lambda )}$

El defecto de ortogonalidad es el producto de las longitudes del vector base dividido por el volumen del paralelepípedo;

${\displaystyle \delta (B)={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{\sqrt {\det(B^{T}B)}}}={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{d(\Lambda )}}}$

De la definición geométrica se puede apreciar que con igualdad si y sólo si la base es ortogonal. ${\displaystyle \delta (B)\geq 1}$

Si el problema de reducción de la red se define como encontrar la base con el defecto más pequeño posible, entonces el problema es NP-duro ^{[ cita necesaria ]} . Sin embargo, existen algoritmos de tiempo polinomial para encontrar una base con defecto donde c es una constante que depende únicamente del número de vectores base y la dimensión del espacio subyacente (si es diferente) ^{[ cita necesaria ]} . Esta es una solución bastante buena en muchas aplicaciones prácticas ^{[ cita requerida ]} . ${\displaystyle \delta (B)\leq c}$

En dos dimensiones

Para una base que consta de sólo dos vectores, existe un método de reducción simple y eficiente muy análogo al algoritmo euclidiano para el máximo común divisor de dos números enteros. Como ocurre con el algoritmo euclidiano, el método es iterativo; en cada paso, el mayor de los dos vectores se reduce sumando o restando un múltiplo entero del vector más pequeño.

El pseudocódigo del algoritmo, a menudo conocido como algoritmo de Lagrange o algoritmo de Lagrange-Gauss, es el siguiente:

 Entrada: una base para la celosía . Supongamos que , de lo contrario, cámbielos. ${\textstyle (u,v)}$ ${\textstyle L}$ ${\textstyle ||v||\leq ||u||}$ Salida: Una base con . ${\textstyle (u,v)}$ ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$

 Mientras : # Redondear al entero más cercano  ${\textstyle ||v||<||u||}$ ${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$ ${\textstyle r:=u-qv}$  ${\textstyle u:=v}$  ${\textstyle v:=r}$

Consulte la sección sobre el algoritmo de Lagrange en ^[1] para más detalles.

Aplicaciones

Los algoritmos de reducción de celosía se utilizan en varias aplicaciones teóricas de números modernas, incluido el descubrimiento de un algoritmo de espita para . Aunque determinar la base más corta es posiblemente un problema NP-completo, algoritmos como el algoritmo LLL ^[2] pueden encontrar una base corta (no necesariamente la más corta) en tiempo polinómico con un rendimiento garantizado en el peor de los casos. LLL se utiliza ampliamente en el criptoanálisis de criptosistemas de clave pública . ${\displaystyle \pi }$

Cuando se utiliza para encontrar relaciones enteras, una entrada típica al algoritmo consiste en una matriz de identidad aumentada con las entradas en la última columna que consisten en los elementos (multiplicados por una constante positiva grande para penalizar los vectores que no suman cero) entre los cuales Se busca relación. ${\displaystyle n\times n}$ ${\displaystyle n}$ ${\displaystyle w}$

El algoritmo LLL para calcular una base casi ortogonal se utilizó para demostrar que la programación entera en cualquier dimensión fija se puede realizar en tiempo polinómico . ^[3]

Algoritmos

Los siguientes algoritmos reducen las bases de la red; También se enumeran varias implementaciones públicas de estos algoritmos.

Referencias

1. Nguyen, Phong Q. (2009). "Algoritmos de celosía y constante de Hermite". El algoritmo LLL . Seguridad de la Información y Criptografía. Berlín, Heidelberg: Springer Berlín Heidelberg. págs. 19–69. doi :10.1007/978-3-642-02295-1_2. ISBN 978-3-642-02294-4. ISSN  1619-7100.
2. 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. 
3. Lenstra, hijo, HW (1983). "Programación entera con un número fijo de variables". Matemáticas de la Investigación de Operaciones . 8 (4): 538–548. CiteSeerX 10.1.1.431.5444 . doi :10.1287/moor.8.4.538. 
4. Hanrot, Guillaume; Stehlé, Damien (2008). "Bases de celosía reducidas de Hermite-Korkine-Zolotarev en el peor de los casos". arXiv : 0801.3331 [matemáticas.NT].
5. Seysen, Martín (septiembre de 1993). "Reducción simultánea de una base reticular y su base recíproca". Combinatoria . 13 (3): 363–376. doi :10.1007/BF01202355. S2CID  206791637.