Polynomial-time binary realization of native LLL below a fixed dimension cutoff
ProvedInfoLossLAR.WorstCase.RegevSketch.finite_cutoff_lll_polyalgorithmslar-regev-bridgelattices
Fix a natural number . There exists one deterministic polynomial-time program on nested lists of integers that realizes the specified native integer LLL reducer in every dimension .
For each nonsingular integer square matrix of dimension , let list the rows of , and let be the basis returned by the native LLL routine. The program satisfies
The running time is polynomial in the full binary length of the encoded list. This supplies the preprocessing step for exact lattice enumeration in a fixed range of dimensions.
Preamble
import Definitions.Def_LARLLL_CurrentData import Definitions.Def_QuantumMaxCutFiniteNumericRuntime set_option autoImplicit false open InfoLossLAR.WorstCase open scoped BigOperators
Formal statement
namespace InfoLossLAR.WorstCase.RegevSketch
theorem finite_cutoff_lll_poly (cutoff : ℕ) :
∃ reduce : List (List ℤ) → List (List ℤ),
OAI.MetricKMedian.Binary.Automatic.Poly reduce ∧
∀ n : ℕ, 1 ≤ n → n < cutoff →
∀ B : Matrix (Fin n) (Fin n) ℤ, B.det ≠ 0 →
reduce (List.ofFn (fun i => List.ofFn (B i))) =
List.ofFn (fun i => List.ofFn ((NativeLLL.basis B) i)) := by sorry
end InfoLossLAR.WorstCase.RegevSketchSource
A.K. Lenstra, H.W. Lenstra Jr. and L. Lovász, Factoring Polynomials with Rational Coefficients, Math. Ann. 261 (1982), §1, https://doi.org/10.1007/BF01457454, algorithm (1.15) and Proposition (1.26). The concrete output of the native reducer and the finite cutoff are formalization-specific.