El procedimiento de transformar una base dada de un retículo (un subgrupo aditivo discreto de R^n generado por combinaciones lineales enteras de vectores base) en una base cuyos vectores son más cortos y más próximos a la ortogonalidad, conservando el mismo retículo.

Principio

Aplicar operaciones unimodulares que preserven la integridad entera para reducir longitudes de vectores y mejorar la ortogonalidad medida por coeficientes Gram–Schmidt; algoritmos prácticos (LLL, BKZ, reducción de Minkowski) equilibran calidad de reducción y tiempo de ejecución y buscan aproximar problemas de vector más corto o mínimos sucesivos.

Demostración

Ejemplo en Z^2: base b1 = (4,1), b2 = (1,3). Operaciones de reducción de tamaño y Gram–Schmidt pueden transformar esto en una base reducida donde un vector sea (1,3) y el otro un par más corto y casi ortogonal; aplicar LLL a una base entera 4×4 a menudo revela vectores mucho más cortos que facilitan problemas de retículo (CVP/SVP).

Aplicación incorrecta

Suponer que un algoritmo de reducción en tiempo polinomial encontrará siempre el vector más corto real (SVP) o tratar cualquier base reducida como única; usar Gram–Schmidt con aritmética en coma flotante sin control puede romper la integridad entera y conducir a conclusiones erróneas.

Consecuencia

Una base reducida suele acelerar algoritmos sobre retículos, proporciona vectores cortos útiles para criptoanálisis o relaciones enteras y ofrece aproximaciones canónicas a los mínimos sucesivos; la calidad de la reducción influye directamente en la resolubilidad de problemas difíciles en retículos.

Inversión

La noción inversa es la expansión de base o la diagonalización ortogonal que no preserva el retículo (ortonormalización real): tales operaciones destruyen la integridad entera y la estructura discreta, a diferencia de las transformaciones unimodulares que sí preservan el retículo.

Límite

Se aplica a retículos en R^n dados por bases enteras y transformaciones unimodulares; excluye grupos aditivos no discretos, módulos sobre anillos distintos de Z salvo adaptación y procedimientos que cambian el retículo (cambios no unimodulares).

Tensión semántica

Hay tensión entre la ortogonalización euclidiana (QR/Gram–Schmidt real) y la reducción de retículos: la primera optimiza la ortogonalidad pero ignora la integridad, la segunda preserva la estructura entera a costa de solo aproximar la ortogonalidad y los vectores más cortos.

Síntesis

La reducción de base de retículo es la aplicación controlada de transformaciones unimodulares enteras y operaciones de reducción de tamaño para producir una base del mismo retículo cuyos vectores sean más cortos y más ortogonales en un sentido medido, equilibrando coste computacional y cercanía a soluciones de SVP/SIVP.