Cofactor canonicalisation of mpn_gcdext

[abbott]

Hi Torbjorn,

You offered these options for the return value of s in mpn_gcdext
(A)  0 <= 2|s| <= |v|/g     except when both inputs are in {-1,0,+1}
(B)  0 <= s <= |v|/g
(C)  0 <= |s| <= |v|/g

You also observed that: 
> Functions in mpn are supposed to do just the work most callers
> care about, and leave fine adjustments to callers that care.


My least favourite is option (C) because it allows "ambiguity": there are
always two possible valid values for s.

I do not much like (B) either because it may force s to take a large value
when a much smaller one (in magnitude) would be allowed by (A).  For example
gcdext(999,1000)  would have to produce s = 999 and t = -998 using rule (B),
whereas rule (A)  would require s = -1 and t = 1.

I like (A) because it guarantees the smallest cofactors (in magnitude).
Rule (A) presumably also has the advantage of being "backwards compatible"
with older versions of GMP.

My preference definitely lies with rule (A), provided that it is not
significantly more costly than (B).  I would reject rule (C).
[Frankly I find it hard to imagine how rule (A) could be significantly
more costly to implement that rule (B), but I could be wrong...]

Hope this helps,
John.