Cofactor canonicalisation of mpn_gcdext

[Bill Allombert]

On Tue, Nov 24, 2009 at 01:17:07PM +0100, Niels Möller wrote:
> abbott <abbott at dima.unige.it> writes:
> 
> > Since you want to document without referring to t, could you not simply say that
> >   if |v/g| = 2 then s=1
> >   otherwise   2 |s| < |v/g|
> >   [note that s=0 iff input is of the form (K*N,N) for some integer K]
> 
> Sounds very reasonable, if that is indeed correct.
> 
> For the case u = v, you prefer s = 0, t = 1 rather than s = 1, t = 0?

The "expected" answer is s=0, t=1 save for u=v=0, in which case it is s=t=0.

> Bill> The most canonical value for s,t is such that -t/s is the one-but-last
> Bill> convergent of the continued fraction associated to u/v.
> 
> I think the corresponding continued fraction expansion would be
> 
>   u/v = 1/1 = 1 / (1 + 0),

Actually it is u/v=1 so there is no one-but-last convergent.  I probably need
to come with a simpler definition, but in fact the Extended GCD is equivalent
to various other algorithms that all look at the action of SL2(Z) over Z^2.

Cheers,
Bill.