next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
LLLBases :: LLLBases

LLLBases -- lattice reduction (Lenstra-Lenstra-Lovasz bases)

Description

LLLBases is a package implementing several variants of LLL bases. Some of these are implemented in the Macaulay2 engine, some by Victor Shoup's NTL package, and some are implemented at top level.

A matrix over ZZ determines a lattice: this is the ZZ-module generated by the columns. It also determines a generating set. See the book: [H. Cohen, ...] for the definition and the basic algorithms for computing LLL bases.

LLL bases have nice theoretical properties, but the main benefit of LLL bases is that the entries of the resulting matrix often have dramatically small size, even smaller than theory would imply.

This package implements the following functions.

Author

Version

This documentation describes version 1.1 of LLLBases.

Source code

The source code from which this documentation is derived is in the file LLLBases.m2.

Exports

  • Functions and commands
    • gcdLLL -- compute the gcd of integers, and small multipliers
    • gramm (missing documentation)
    • hermite (missing documentation)
    • isLLL -- is a basis an LLL basis?
    • kernelLLL (missing documentation)
    • LLL -- compute an LLL basis
  • Symbols
    • BKZ -- compute BKZ reduced basis instead of an LLL reduced basis
    • CohenEngine -- use the original Macaulay2 LLL algorithm
    • CohenTopLevel -- use the Macaulay2 language LLL algorithm
    • fpLLL (missing documentation)
    • Givens -- use Givens rotations instead of Gram-Schmidt during LLL
    • Hermite (missing documentation)
    • NTL -- use the all-integer LLL strategy from NTL library
    • RealFP -- use double precision real numbers
    • RealQP -- use quadruple precision real numbers
    • RealQP1 -- use a combination of double precision and quad precision real numbers
    • RealRR -- use arbitrary precision real numbers
    • RealXD -- use extended exponent real numbers
    • Threshold -- the LLL threshold, in interval (1/4,1]

Menu

main LLL algorithm

applications and variants

support routines that are occasionally useful