##  [Lattice Basis Reduction](/lattice-basis-reduction-0) 

 Definition

The procedure of transforming a given basis of a lattice (a discrete additive subgroup of R^n generated by integer linear combinations of basis vectors) into a basis whose vectors are shorter and closer to orthogonal while spanning the same lattice.

 

 

 

 

 

 





## Principle

Principle

Apply integer-preserving unimodular column operations to decrease vector lengths and improve orthogonality measured by Gram–Schmidt coefficients; practical algorithms (LLL, BKZ, Minkowski reduction) trade off reduction quality and running time and aim to approximate shortest-vector or successive minima problems.

 

 

 

 

 





## Demonstration

Demonstration

Example in Z^2: basis b1 = (4,1), b2 = (1,3). Gram–Schmidt and size-reduction operations can transform this into a reduced basis where one vector is (1,3) and the other is (3, -1) or a similarly shorter, more orthogonal pair; applying LLL to a concrete 4×4 integer basis often reveals much shorter vectors that make lattice problems (CVP/SVP) computationally easier.

 

 

 

 

## Misapplication

Misapplication

Assuming a polynomial‑time reduction algorithm will always find the true shortest vector (SVP) or treating any reduced basis as unique; using floating‑point Gram–Schmidt without control may break lattice integrality and lead to incorrect conclusions.

 

 

 

 

 





## Consequence

Consequence

A reduced basis typically accelerates lattice algorithms, yields short lattice vectors useful for cryptanalysis or integer relations, and provides canonical approximations to successive minima; quality of reduction directly affects solvability of hard lattice problems.

 

 

 

 

## Reversal

Reversal

The inverse notion is basis expansion or orthogonal diagonalization that does not preserve the lattice (real orthonormalization) — such operations destroy integrality and the discrete structure, unlike unimodular transformations which preserve the lattice.

 

 

 

 

 





## Boundary

Boundary

Applies to lattices in R^n given by integer bases and unimodular transformations; excludes non-discrete additive groups, modules over rings other than Z unless adapted, and procedures that change the lattice (non-unimodular changes).

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension arises between Euclidean orthogonalization (real-valued QR/Gram–Schmidt) and lattice reduction: the former optimizes orthogonality but ignores integrality, while lattice reduction preserves the discrete integer structure at the cost of only approximating true orthogonality and shortest vectors.

 

 

 

 

 





## Synthesis

Synthesis

Lattice basis reduction is the controlled application of integer unimodular transformations and size‑reduction to produce a basis of the same lattice whose vectors are shorter and more orthogonal in a measured sense, balancing computational cost against closeness to SVP/SIVP solutions.