Lattices-0.0.1: A library for lattices



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



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