Cofactor canonicalisation of mpn_gcdext

Niels Möller nisse at
Tue Nov 24 13:17:07 CET 2009

abbott <abbott at> 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?

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),

but since I'm not so familiar with that topic I'm not sure what the
"one-but-last convergent" is,


More information about the gmp-devel mailing list