mpn_gcdext

[Victor Shoup]

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:

>        Hi,
>
> 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