Math.Lattices.LLL

Implements a *very* basic LLL (Lenstra-Lenstra-Lovsz) 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 Lszl Lovsz. 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 Jrgen Gerhard. Chapter 16.

References for Babai's Nearest Plane Method for the Closest Vector Problem:

• On Lovsz' Lattice Reduction And The Nearest Lattice Point Problem, Lszl Babai. Combinatorica 6 (1), 1-13 (1986).
• Mathematics of Public Key Cryptography, Steven Galbraith. Chapter 18 of draft 1.0

Documentation

lll :: [[Rational]] -> Basis

Just an easy way to write $||v||^2$

Closest 'Integral to the given n, rounding up. $lfloor nrceil$

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

closeVector :: [[Rational]] -> [Ratio Integer] -> [Rational]

Find a lattice vector in 'basis close to x. basis is assumed to be LLL-reduced

type Basis = Array Int [Rational]

A matrix representing a basis