### 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 shortest multipliers. Our algorithm is described here.

There is a slight difference between the output here and that of our earlier shortest multiplier program. For instead of finding all multipliers of length not exceeding B_{m} and then determining the shortest ones, we now repeatedly replace B_{m} by a smaller one until no shorter multiplier is produced, in which case we then output all shortest multipliers.

*Last modified 24th October 2011*

Return to main page