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

Here d₁,...,d_m are positive integers. We find small multipliers y₁,...,y_m such that gcd(d₁,...,d_m)=y₁d₁+···+y_md_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₁,...,x_m) such that x₁d₁+⋯+x_md_m = 0.
The last row of B gives the small multipliers y₁,...,y_m.

We use a modification of the Fincke-Pohst algorithm to determine all multipliers Y such that ||Y||² ≤ ||B_m||² and hence find all shortest multipliers. Our algorithm is described here.

Last modified 29th April 2016
Return to main page