Cofactor canonicalisation of mpn_gcdext

[abbott]

Hi Niels,

> One other observation, before I get to the main part of this posting:
> It is clear that there exists an s in the range 2 |s| < |v/g|, but it
> wasn't clear to me that this is what's naturally produced by Euclid's
> algorithm;

I didn't know it either but it can be proved,
see Theorem 4.3(vi) page 78 in Shoup's book:
    http://www.shoup.net/ntb/


Personally, I am currently more interested in mpz_gcdext than in
mpn_gcdext.  For mpz_gcdext I have strong preference (as indicated
in my previous email) for s to satisfy   2|s| < |v/g|.  Since the
mpn_* functions are intended to deal with non-negative integers, I can
see that for mpn_gcdext it might be more convenient to guarantee
that s is non-negative (and t non-positive).  It would certainly be
technically possible to specify that the (s,t) values computed by
mpn_gcdext satisfy one criterion, and those produced by mpz_gcdext
satisfy a different criterion -- I do some have doubts about how
desirable such a situation would be, though.

John.