Math.Lattices.LLL

Implements a *very* basic LLL (Lenstra-Lenstra-Lovász) lattice reduction algorithm. This version uses exact arithmetic over the rationals. References for the LLL algorithm:

• Factoring Polynomials with Rational Coefficients, Arjen K Lenstra, Hendrik W Lenstra Jr, and László Lovász. Mathematische Annalen 261, 515-534 (1982)
• Mathematics of Public Key Cryptography, Steven Galbraith. Chapter 17 of draft 1.0
• Modern Computer Algebra, second edition, Joachim von zur Gathen and Jürgen Gerhard. Chapter 16.

Documentation

lll :: [[Rational]] -> Basis

Return an LLL reduced basis. This calls 'lllDelta with a default parameter $delta = 3/4$

lllDelta :: [[Rational]] -> Rational -> Basis

Return an LLL reduced basis, with reduction parameter $delta$. This is the conventional flavor of the algorithm using Gram-Schmidt, no fancy speedups yet

type Basis = Array Int [Rational]

A matrix representing a basis