Cofactor canonicalisation of mpn_gcdext

[abbott]

Niels> Sounds very reasonable, if that is indeed correct.

I believe it is correct, but it would be nice if someone else could check it...
errare humanum est!


Niels> For the case u = v, you prefer s = 0, t = 1 rather than s = 1, t = 0?

I do not have any strong preference.  I was following Shoup's approach:
he gave an explicit definition of (extended) Euclid's Algorithm, and then
described the behaviour of that specific explicit algorithm.

At the moment I do not see any technical argument which favours (s=0,t=1)
over (s=1,t=0) or vice versa.  In the absence of a good reason to do
otherwise, I would follow Shoup: ShoupEEA gives s=1 if the input is (0,0)
and s=0 if the input is (N,N) for non-zero N.


John>  [if u = v then]... s=0

Niels> For the case u = v, you prefer s = 0, t = 1 rather than s = 1, t = 0?

Torbjörn> At the mpn level, we might choose not to pin things down for degenerate
Torbjörn> cases, unless it can be done for free.

Maybe the degenerate input (0,0) should be handled specially?

I think that specifying  s = 0  when  u = v  will give the simplest code
(if the underlying implementation follows Shoup's definition of EA).

I think the documentation should be explicit about the border cases but it
could also point out that in those cases there are equally valid alternative
outputs, and that the specific choice of valid output could potentially change
in future versions of GMP (e.g. when someone finally submits an FFT-based
extended half-gcd for parallel quantum computers which happens to handle
border cases differently).

John.