Module lattice 

LLL lattice reduction — the geometric lens of the compression campaign.

Every rung so far reads structure through a finite field: linear/algebraic/correlation attacks are linear algebra or statistics over GF(2), GF(p), GF(2ⁿ). Lattice reduction reads it through the GEOMETRY OF NUMBERS instead — an orthogonal lens. A lattice is the integer span of a basis; its short vectors are its most compressed representatives, and a SHORT vector is a hidden small relation among the basis rows. So “find the shortest vector” is exactly “find the maximal compression,” and the symmetry being broken is the lattice’s own geometry rather than a field’s algebra.

This is the lens that reaches the cryptographic weaknesses the field-based rungs cannot express: an RSA key that is structured but not factorable by Fermat — small hidden roots (Coppersmith), partial key exposure, a private exponent below Wiener’s bound (Boneh–Durfee d < N^0.292) — leaks a short lattice vector even when no factoring shortcut exists. It is a different game than factoring: the compression game, played on the reals. lll_reduce is that lens; Coppersmith’s small-roots method is built on top of it.

The reduction is EXACT — Gram–Schmidt over [Rational], no floating point — so its output is a certified reduced basis, not a numerical approximation.

Functions

lll_reduce

LLL-reduce an integer lattice basis (the rows of basis), returning a reduced basis of the same lattice with short, nearly-orthogonal vectors. Exact arithmetic throughout (Gram–Schmidt over the rationals, size reduction with |μ| ≤ ½, the Lovász swap at δ = ¾), so the result is a certified LLL-reduced basis. The first row is a short vector — for a lattice built to encode a cryptographic weakness, that short vector is the leaked secret.

lll_reduce_bigint

LLL-reduce a BigInt lattice basis — the entry point for lattices with huge entries, such as the N^m-scaled rows of Coppersmith’s method. The symmetry that makes this fast: only the BASIS need be exact; the Gram–Schmidt that steers the size-reductions and Lovász swaps runs in floating point, so there is no rational coefficient blow-up. The reduced basis is still exact integer, and correctness is re-checked downstream (a Coppersmith root either divides N or it does not).

lll_reduce_bigint_exact

Exact integer LLL (Cohen, A Course in Computational Algebraic Number Theory, Algorithm 2.6.3): the Gram–Schmidt quantities are tracked as EXACT integers (the sub-determinants dᵢ and the scaled coefficients λᵢⱼ = dⱼ·μᵢⱼ), with Bareiss-style exact division — no floating point (so no precision loss on high-dynamic-range lattices) and no rationals (so no coefficient blow-up). This is the trustworthy reduction the Boneh–Durfee independence diagnosis needs.

lll_reduce_bigint_fp

The L² lattice reduction (fpLLL): LLL with a BigFloat Gram–Schmidt — fast like floating point, but with FP_PREC bits of precision so it survives the high dynamic range of Coppersmith/Boneh–Durfee lattices where f64 fails, and without the determinant blow-up of the exact integer LLL. The basis stays exact integer; only the steering is in BigFloat, and swaps update the Gram–Schmidt incrementally (O(n³) overall rather than the O(n⁵) of recompute-on-swap).