Keith Matthews' LLL page

Solving problems with the LLL algorithm (Mark van Hoeij)

LLL lecture by Oded Regev, 2004

Selected applications of LLL in number theory ( Denis Simon)

Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications, Murray R. Bremner, CRC Press 2011

Extended gcd and Hermite normal form algorithms via lattice basis reduction, G. Havas, B.S. Majewski, K.R. Matthews, Experimental Mathematics, Vol 7 (1998) 125-136.

These algorithms experimentally have the following properties:
(a) small multipliers are obtained for the extended gcd problems and more generally
(b) small unimodular transformation matrices are obtained for the Hermite normal form of an mxn matrix A.
The algorithms were inspired by limiting versions of LLL applied to [I_m|NⁿA₁|···|NA_n] as N gets large. The three LLLGCD algorithms are available in CALC, as is the LLLHNF algorithm. They are also online as BCMATH programs. Also see addenda.

Short solutions of AX=B using a LLL-based Hermite normal form algorithm (pdf 123K) (18th August 1998)

This uses the Havas, Majewski, Matthews HNF algorithm to test for solubility in integers of a system of integer linear equations. A short solution is also found in the case of solubility. (The algorithm is available in my CALC program as axb().)

Short multipliers for the extended gcd problem (pdf 182K) (11th January 2001)

This is a heuristic algorithm which usually delivers shorter multipliers than the one found by the LLL-based method. It will produce the shortest multipliers for 3 numbers and the shortest multipliers in this case are fully described. The algorithm is available in my CALC program as lllgcd0().

Slides for a LLL gcd/Hermite normal form seminar (pdf)

These were given at TU München and 13th Czech-Slovak Number Theory Conference, Ostravice, September 1997.

LLL extended GCD algorithm examples

LLL Hermite normal form algorithm example

• 4x4 (10th July 1997 noticed and replaced missing part on 6th Feb 2007)

Minimal multipliers for consecutive Fibonacci numbers, K.R. Matthews, Acta Arith. 75 (1996) 205-218.

The LLL gcd algorithm above always produces the shortest multipliers when the input are m consecutive Fibonacci numbers. With much experimentation and guesswork, I found formulae for these shortest multipliers involving the integer part symbol.

After 14 years, on writing a BCMATH version of the CALC code, I realised that the pseudo code had errors. Latest version 15/09/2011) MLLL pseudocode (implemented in CALC.)

This is an implementation of the original algorithm of M. Pohst in his paper A modification of the LLL-algorithm, J. Symbolic Computation 4 (1987) 123-128

Smith normal form with MLLL

At George Havas' suggestion in 1992, I wrote a program to use the MLLL algorithm to prevent coefficient explosion in obtaining the Smith canonical form of an integer matrix. The idea is simple but effective - bring in MLLL when the coefficients exceed a prescribed limit. This usually results in very small row vectors, often unit vectors and is implemented in my CALC program. In practice one gets unimodular P and Q with smallish entries such that PAQ=SNF(A).
The exact integer arithmetic involved in the underlying Gram-Schmidt process slows things down for large matrices of size bigger than (say) 150x300.

BCMATH LLL-based integer matrix programs

Last modified 10th April 2024