Cofactor canonicalisation of mpn_gcdext

Bill Allombert Bill.Allombert at math.u-bordeaux1.fr
Mon Nov 23 23:13:09 CET 2009


On Sun, Nov 22, 2009 at 10:02:35PM +0100, Niels Möller wrote:
> One other observation, before I get to the main part of this posting:
> It is clear that there exists an s in the range 2 |s| < |v/g|, but it
> wasn't clear to me that this is what's naturally produced by Euclid's
> algorithm; I'm more familier with the bounds |s| < |v|/g, or the

The most canonical value for s,t is such that -t/s is the one-but-last
convergent of the continued fraction associated to u/v.

Cheers,
Bill.


More information about the gmp-devel mailing list