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
Around 1992, I worked with George Havas, applying the LLL algorithm to finding small multipliers for the extended gcd problem. We also developed a LLL type algorithm for obtaining small unimodular transformation matrices for the Hermite normal form of an integer matrix.
 Extended gcd and Hermite normal form algorithms via lattice basis reduction, G. Havas, B.S. Majewski, K.R. Matthews, Experimental Mathematics, Vol 7 (1998) 125136.
 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^{n}A_{1}···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 LLLbased 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 LLLbased 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 CzechSlovak 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) 205218.
 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 LLLalgorithm, J. Symbolic Computation 4 (1987) 123128
 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 GramSchmidt process
slows things down for large matrices of size bigger than (say) 150x300.
 BCMATH LLLbased integer matrix programs
Last modified 10th April 2024