Cofactor canonicalisation of mpn_gcdext
Bill Allombert
Bill.Allombert at math.u-bordeaux1.fr
Tue Nov 24 23:26:54 CET 2009
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.
More information about the gmp-devel
mailing list