Resultados del cálculo
Reducción LLL de bases de retículos - definición, ejemplos y práctica
This guide explains the LLL (Lenstra–Lenstra–Lovász) lattice basis reduction algorithm, gives the defining conditions and formulas, provides worked examples, highlights common mistakes, and supplies practice problems with foldable answers. It is intended as companion content for a Matrix LLL Reduction Calculator.
¿Qué es la reducción LLL?
The LLL algorithm produces a reduced basis for a lattice given an initial basis matrix \[ B = [\mathbf{b}_1,\mathbf{b}_2,\ldots,\mathbf{b}_n] \] by combining Gram–Schmidt orthogonalization, size reduction, and the Lovász condition. The reduced basis tends to have shorter, more orthogonal vectors and is computed in polynomial time.
The output of LLL is generally not unique: different implementations, the chosen reduction parameter \(\delta\) (commonly \(0.99\) or \(3/4\)), the order of basis vectors, tie-breaking rules, or small numerical roundings can lead to different but equally valid LLL-reduced bases. Therefore the calculator may return one valid reduced basis; other correct reduced bases may exist that satisfy the LLL conditions.
Condiciones formales (resumen)
For a basis \(\{\mathbf{b}_1,\dots,\mathbf{b}_n\}\) and its Gram–Schmidt vectors \(\{\mathbf{b}_1^*,\dots,\mathbf{b}_n^*\}\), define
$$ \mu_{i,j}=\frac{\langle \mathbf{b}_i,\mathbf{b}_j^* \rangle}{\|\mathbf{b}_j^*\|^2},\qquad j- Size reduction: \(|\mu_{i,j}|\le 1/2\) for all \(j
- Lovász condition: \((\delta - \mu_{i,i-1}^2)\|\mathbf{b}_{i-1}^*\|^2 \le \|\mathbf{b}_i^*\|^2\) for \(i=2,\dots,n\).
Ejemplo resuelto 1
Dada la matriz base
One possible LLL-reduced basis (depending on \(\delta\) and tie-breaking) is:
Una matriz reducida por LLL válida (una posible salida):
\[ A_{\text{LLL}} = \begin{pmatrix} 2 & 3 \\ 0 & 3 \end{pmatrix} \]Note: this is one possible reduced basis. Other implementations or parameter choices may produce a different reduced basis that still satisfies the LLL conditions.
Ejemplo resuelto 2
Dada la matriz base
A continuación se muestra una base reducida por LLL válida:
Reminder: this is one possible valid LLL result. Different but equivalent reduced bases may exist.
Errores comunes
- Incorrect Gram–Schmidt: forgetting orthogonal projections or using unstable floating arithmetic without reorthogonalization.
- Applying only a single pass of size reduction — LLL requires iterative re-checking of the Lovász condition.
- Choosing \(\delta\) outside the allowed range (must be \(0.25 < \delta < 1\)).
- Assuming uniqueness — do not expect the exact same output from all implementations.
Practice Problems (Compute LLL-reduced basis)
For each exercise, a valid LLL-reduced basis is provided as one possible answer. Other correct reduced bases may exist — the calculator may return any valid one.
Ejercicio 1
This is one valid reduced basis. Other LLL outputs are possible depending on \(\delta\) and implementation details.
Ejercicio 2
This is one possible reduced basis. Equivalent LLL outputs may differ by unimodular transformations or sign/order choices.
Ejercicio 3
One valid LLL result; other reduced bases satisfying size-reduction and Lovász conditions may exist.
Ejercicio 4
This is one possible reduced basis. Implementations may produce alternative but valid LLL bases.
Nota práctica para la calculadora: allow the user to select the LLL parameter \(\delta\) (e.g. 0.75 or 0.99) and optionally request a particular tie-breaking / deterministic mode for reproducible outputs. When reporting results, include a short note: “One valid LLL-reduced basis is shown; other valid bases may exist.”
Copyright Notice: This article is original content from the Matrix Calculator website. Please credit the source when sharing or reproducing it. For more matrix computation tools, visit matrixcalcu.com.
El algoritmo LLL también se conecta con la multiplicación de matrices, la forma triangular superior y la descomposición QR.
Aprende multiplicación de matrices más fácilmente en solo 2 minutes with this juego gratuito.
