Lattices-0.0.1: A library for lattices

Math.Lattices.LLL

Description

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.

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

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

Synopsis

# Documentation

lll :: [[Rational]] -> BasisSource

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 -> BasisSource

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]Source

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

type Basis = Array Int [Rational]Source

A matrix representing a basis