Lattices and LLL Reduction
Integral LLL: Avoiding Floating Point
Running LLL entirely in integer arithmetic using scaled Gram-Schmidt quantities, and why this matters for exact downstream computation.
Engineering / MathematicsLattices and LLL Reduction2 min readKV-MATH-0549
Floating-point LLL is faster and fails silently. The integral variant carries scaled Gram-Schmidt quantities as exact integers, which is slower but produces a result that can be trusted inside an exact computation.
The problem with floating point
The integral approach
Rather than storing the rational coefficients directly, store them scaled by the relevant Gram determinants, which makes them integers. All comparisons in the algorithm can then be rewritten as integer comparisons.
Cost
| Variant | Speed | Reliability | Use when |
|---|---|---|---|
| Floating point | Fastest | Can fail silently | Result is verified downstream anyway |
| Integral | Slower, entries grow | Exact | Result feeds an exact computation |
| Floating point with fallback | Fast in the common case | Exact | Best of both, if the check is genuinely exact |
The hybrid pattern
Hybrid floating point and exact LLL
- Reduce in floating pointFast, produces a candidate basis and the transformation matrix.
- Verify exactlyApply the transformation to the exact input and check the reduction conditions in integers.
- Fall backIf verification fails, re-run integrally, or increase precision and retry.
Where exactness is mandatory
Any use inside Hermite normal form computation or polynomial factorisation requires an exact result, because a wrong basis there produces a wrong answer rather than merely a slow one.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 2.6.3. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.