Paul Zimmermann Paul.Zimmermann at
Mon Apr 27 11:43:15 CEST 2009


about mpn_gcdext, Victor Shoup has shown (and I have double-checked) that
if a >= b > 0, then the cofactor s output by the classical extended gcd,
i.e., s*a + t*b = g := gcd(a,b), satisfies -b/(2g) < s <= b/(2g).

Since mpn_gcdext (a, b) exactly requires a >= b > 0, it would be nice if the
output cofactor could satisfy -b/(2g) < s <= b/(2g). In such a way the output
of mpn_gcdext would be uniquely defined.

Paul Zimmermann

More information about the gmp-bugs mailing list