A solution to the extended GCD problem with applications
Arne Storjohann · 1997
This paper considers a variation of the extended gcd problem: the "modulo N extended gcd problem", Given an integer row vector [a, ]~=1.the modulo N extended gcd problem asks for an integer vector [c,]~=l such that n gcd(~c, a,, N) = gcd(al, a~, . ..,a~,N) ,:1 A deterministic algorithm is presented which returns an exceptionally small solution for a given instance of the problem: both ma.x~=~Ic,I and the number of nonzero c,'s will he boundedbyO(logN).The gcd algorithm presented here has numerou supplications andhaa already ledtofasteralgorithms for computing row reduced echelon forms of integer matrices and solving systems of linear Diophantine equations.III this paper we show how to apply our g,cd algorithm to the problem of computing small pre-and post-multipliers for the Smith normal of an integer matrix."'rbis work has been partially supported by grants from the Swiss Federal Ofiice for Education and Sciences in conjunction with partial support by ESPRIT LTR