Reducción de red

Reducción de 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 reticular es encontrar una base con vectores cortos y casi ortogonales cuando se da como entrada una base reticular entera . Esto se logra utilizando diferentes algoritmos, cuyo tiempo de ejecución suele ser al menos exponencial en la dimensión de la red.

Casi ortogonal

Una medida de la casi ortogonalidad es el defecto de ortogonalidad . Este compara el producto de las longitudes de los vectores base con el volumen del paralelepípedo que definen. Para vectores 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 completamente 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 lo conoce como el 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 de los vectores 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 desprende que con igualdad si y sólo si la base es ortogonal. ${\displaystyle \delta (B)\geq 1}$

Si el problema de reducción de red se define como la búsqueda de la base con el menor defecto posible, entonces el problema es NP-hard ^{[ cita requerida ]} . 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 de base y la dimensión del espacio subyacente (si es diferente) ^{[ cita requerida ]} . Esta es una solución suficientemente buena en muchas aplicaciones prácticas ^{[ cita requerida ]} . ${\displaystyle \delta (B)\leq c}$

En dos dimensiones

Para una base formada por sólo dos vectores, existe un método de reducción simple y eficiente, muy similar al algoritmo euclidiano para el máximo común divisor de dos números enteros. Al igual que en 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 menor.

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 red . Suponga que , de lo contrario intercá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 red se utilizan en varias aplicaciones modernas de la teoría de números, incluido el descubrimiento de un algoritmo de espiga 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 polinomial 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 de números enteros, 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 la relación. ${\displaystyle n\times n}$ ${\displaystyle n}$ ${\displaystyle w}$

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

Algoritmos

Los siguientes algoritmos reducen las bases reticulares; también se enumeran varias implementaciones públicas de estos algoritmos.

Referencias

1. Nguyen, Phong Q. (2009). "Algoritmos de constante y red de Hermite". El algoritmo LLL . Seguridad de la información y criptografía. Berlín, Heidelberg: Springer Berlin 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, Jr., 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, Martin (septiembre de 1993). "Reducción simultánea de una base reticular y su base recíproca". Combinatorica . 13 (3): 363–376. doi :10.1007/BF01202355. S2CID  206791637.