lll-rs is an implementation of the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL [LLL82], [1a], [1b]) in Rust.
The library comes with a set of simple helpers to create vectors and matrices, with the following entries:
BigVector, relying on rug::Integer)RationalVector, relying on rug::Rational)VectorF, relying on f64)lll-rs is far from feature-complete and should be considered experimental. Users willing to use a stable and battle-tested library should
consider fplll instead [fplll].
A lattice Λ is a dicrete subgroup of some vector space E. A typical example (see e.g. [3]) is E = ℝⁿ and
X ∊ Λ <=> X = l_1 * b_1 + ... + l_n * b_n with (l_i) in ℤ and (b_i) in ℝ
Lattices are much studied mathematical structures on which we can formulate some useful problems [4]. Some of these problems are simpler to solve when a "good basis" is known for the lattice. Conversely it is difficult to solve them when only a "bad basis" is known.
Simply put, the LLL algorithm provides such a "good basis"; it roughly does so by performing a (variant of) rounded Gram-Schimdt orthogonalization on the "bad basis". Remarkably, this algorithm runs in polynomial time which makes it possible to solve several lattice problems efficiently.
Applications of LLL include:
```rust
// Init the matrix with Integer
let mut basis: Matrix
// Populate the matix basis[0] = BigVector::fromvector(vec![ Integer::from(1) << 100000, Integer::from(0), Integer::from(0), Integer::from(1345), ]); basis[1] = BigVector::fromvector(vec![ Integer::from(0), Integer::from(1), Integer::from(0), Integer::from(35), ]); basis[2] = BigVector::from_vector(vec![ Integer::from(0), Integer::from(0), Integer::from(1), Integer::from(154), ]);
// Perfom the LLL basis reduction biglll::lattice_reduce(&mut basis);
// OR // Perfom the L2 basis reduction // Specify the delta and eta coefficient for the reduction bigl2::lattice_reduce(&mut basis, 0.5005, 0.999); ```
[LLL82] A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz. Factoring polynomials with rational coefficients. Math. Ann., 261: 515–534 (1982)