shoup at cs.nyu.edu
Mon Apr 27 11:55:58 CEST 2009
I would recommend this, but in the mean time,
I'm implementing this logic in NTL's GMP wrapper,
so I don't have to assume anything.
On Apr 27, 2009, at 5:43 AM, Paul Zimmermann wrote:
> 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
> 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