Lattice Mathematics Referenz
Referenz für lattice Theorie: bases, determinants, shortest vector, und LLL reduction.
Lattice Fundamentals
A lattice is the set of all integer linear combinations of basis vectors: L = {sum(zi * bi) : zi in Z}. The determinant det(L) = |det(B)| measures the fundamental parallelepiped volume. The rank is the number of linearly independent basis vectors. The successive minima λi are the lengths of the shortest linearly independent vectors. Minkowski's theorem bounds λ1 by sqrt(n) * det(L)^(1/n). The shortest vector problem (SVP) and closest vector problem (CVP) are fundamental hard problems. Lattices appear in cryptography (LWE, NTRU) and number theory.
- basis
- Integer combinations
- determinant
- Parallelepiped volume
- SVP
- Shortest vector
generates lattice|det(B)|hard problemReduction and Hard Problems
LLL reduction produces a nearly-orthogonal basis in polynomial time, approximating SVP within 2^(n/2). BKZ reduction generalizes LLL with block size β for better approximation at higher cost. The Gaussian heuristic estimates λ1 ≈ sqrt(n/(2*pi*e)) * det(L)^(1/n). SVP is NP-hard under randomized reductions; CVP is NP-hard. The Learning With Errors (LWE) problem reduces to worst-case lattice problems (GapSVP, SIVP). Quantum algorithms (Grover) provide only quadratic speedup for lattice problems, unlike Shor for factoring. This makes lattices post-quantum secure.
- LLL
- Polynomial reduction
- BKZ
- Block reduction
- LWE
- Reduces to lattice
2^(n/2) approxbetter approxpost-quantum