Reducción de la red

En matemáticas, el objetivo de la reducción de bases reticulares es encontrar una base con vectores cortos y casi ortogonales a partir de una base reticular entera . Esto se logra mediante diferentes algoritmos, cuyo tiempo de ejecución suele ser al menos exponencial con respecto a la dimensión de la red.

Encontrar una base reticular reducida también está estrechamente relacionado con el problema de la cristalografía de hallar una celda unitaria única. Históricamente, la teoría de la reducción fue estudiada por primera vez por Lagrange (1773) e independientemente por Gauss (1801), con el fin de clasificar las formas cuadráticas binarias , un problema clásico de la teoría de números. En una breve nota al margen de una reseña de un libro en 1831, Gauss menciona que la teoría de la reducción para ciertas formas cuadráticas es equivalente a encontrar una celda unitaria para redes de puntos y reconoce su relevancia para la cristalografía. Esta estrecha relación entre la teoría de números y la geometría de las redes de puntos inspiró gran parte del trabajo posterior sobre formas cuadráticas, que culminó en la importante obra de Minkowski , "Geometría de los números" (1896 y 1910).

Una medida de ortogonalidad aproximada 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 iguales.

Cualquier base particular de${\displaystyle n}$Los vectores pueden representarse mediante una matriz.${\displaystyle B}$, cuyas columnas son los vectores base${\displaystyle b_{i},i=1,\ldots ,n}$En el caso de dimensión completa , 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.${\displaystyle \det(B)}$. Si el número de vectores es menor que la dimensión del espacio subyacente, entonces el volumen es${\displaystyle {\sqrt {\det(B^{T}B)}}}$Para una red dada${\displaystyle \Lambda }$Este volumen es el mismo (salvo signo) para cualquier base y, por lo tanto, se denomina determinante de la red.${\displaystyle \det(\Lambda)}$o constante de red${\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 )}}}$

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

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

Para una base compuesta por solo dos vectores, existe un método de reducción sencillo y eficiente, muy similar al algoritmo euclidiano para el máximo común divisor de dos enteros. Al igual que el algoritmo euclidiano, el método es iterativo; en cada paso, el vector mayor 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:

 Aporte:${\textstyle (u,v)}$una base para la red${\textstyle L}$. Supongamos que${\textstyle ||v||\leq ||u||}$, de lo contrario, intercámbialos. Salida: Una base${\textstyle (u,v)}$con${\textstyle ||u||=\lambda _ {1}(L),||v||=\lambda _ {2}(L)}$.

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

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

Los algoritmos de reducción de retículos se utilizan en una serie de aplicaciones modernas de teoría de números, incluido el descubrimiento de un algoritmo de espiga para${\displaystyle \pi }$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 sistemas criptográficos de clave pública .

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

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 polinomial . ^{[ 4 ]}

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