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 multipliers Y such that ||Y||2 ≤ ||Bm||2 and hence find all shortest multipliers. Our algorithm is described here.
Last modified 29th April 2016
Return to main page