2 unstable releases

0.2.0	Apr 6, 2020
0.1.0	Feb 22, 2020

#558 in Math

MIT and LGPL-3.0+

34KB
670 lines

lll-rs

lll-rs is an implementation of the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL [LLL82], 1a, 1b) in Rust.

Supported algorithms

LLL reduction 1a
L² reduction 2
Standard Gram-Schmidt orthogonalisation

The library comes with a set of simple helpers to create vectors and matrices, with the following entries:

Integers (BigVector, relying on rug::Integer)
Rationals (RationalVector, relying on rug::Rational)
Small rationals (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.

Lattice reduction

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:

Cryptanalysis of lattice-based cryptosystems (e.g. NTRU)
Cryptanalysis of pseudo-random number generators (e.g. LCG and truncated LCG)
Cryptanalysis of RSA (e.g. Coppersmith's attack 5)
Cryptanalysis of knapsack-based cryptosystems
Finding mathematical counterexamples (e.g. Merten's conjecture)
Finding roots of polynomials with integer coefficients
Finding integer relations between constants
Decoding of error correcting codes

Example

// Init the matrix with Integer
let mut basis: Matrix<BigVector> = Matrix::init(3, 4);

// Populate the matix
basis[0] = BigVector::from_vector(vec![
    Integer::from(1) << 100000,
    Integer::from(0),
    Integer::from(0),
    Integer::from(1345),
]);
basis[1] = BigVector::from_vector(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);

References and documentation

[LLL82] A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz. Factoring polynomials with rational coefficients. Math. Ann., 261: 515–534 (1982)

Dependencies

~2.5MB
~47K SLoC