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

Here d1,...,dm are positive integers. We find small multipliers y1,...,ym such that gcd(d1,...,dm)=y1d1+···+ymdm,
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 (x1,...,xm) such that x1d1+⋯+xmdm = 0.
The last row of B gives the small multipliers y1,...,ym.

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 Bm and then determining the shortest ones, we now repeatedly replace Bm by a smaller one until no shorter multiplier is produced, in which case we then output all shortest multipliers.

Enter the positive integers (separated by spaces):

Last modified 1st November 2022
Return to main page