### Finding small multipliers for the extended gcd problem using the Havas-Majewski-Matthews LLL-based method

Here d_{1},...,d_{m} are positive integers. We find small multipliers y_{1},...,y_{m} such that gcd(d_{1},...,d_{m})=y_{1}d_{1}+···+y_{m}d_{m},

using the LLLGCD method of *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 with parameter α = 1. (See slides and corrections to paper.) Also see the examples and *Lattice Basis Reduction: An Introduction to the LLL Algorithm and Its Applications*, Murray R. Bremner, CRC Press 2011.
The output is an m x m unimodular integer matrix B, whose first m-1 rows form a basis for the lattice formed by the integer vectors (x_{1},...,x_{m}) such that x_{1}d_{1}+⋯+x_{m}d_{m} = 0.

The last row of B gives the small multipliers y_{1},...,y_{m}.

We use a modification of the Fincke-Pohst algorithm to determine all multipliers Y such that ||Y||^{2} ≤ ||B_{m}||^{2} and hence find all shortest multipliers. Our algorithm is described here.

*Last modified 29th April 2016*

Return to main page