Cofactor canonicalisation of mpn_gcdext
nisse at lysator.liu.se
Tue Nov 24 11:58:17 CET 2009
abbott <abbott at dima.unige.it> writes:
> I looked through Shoup's arguments (and exercise 4.9), and concluded the
> following: strict inequality is guaranteed whenever lambda >= 3.
> I then looked at the various cases where lambda was small.
> In summary, strict inequality is guaranteed except for the
> following inputs (a,b) and assuming a >= b >= 0
> (0,0) very special case
> (N,0) trivial case
> (N,N) another trivial case
> (2*N,N) very easy case
> (K*N,2*N) with K >= 3 and K odd
> As Niels noted the only cases where strict inequality fails are where
> |s| = 1 or |t| = 1.
This summary agrees with my analysis. For the examples I found where
strict inequality failed, the offending number was s = 1 or t = 1;
don't think s = -1 or t = -1 can violate the strict inequality.
> I admit I am a little puzzled about why it is important that the
> inequality 2*|s| < |v/g| be strict.
It's not very important in itself. The point is that it would be nice
to describe the expected return value (in the GMP interface
documentation as well as in the testsuite) in a way that defines s
uniquely. Current documentation does not, and that's a source of the
> In summary I think we can have both (A) and (B) together because
> * Shoup's Thm 4.3(vi) gives us the non-strict inequalities
> * the two non-strict inequalities together determine s & t uniquely
Since the underlying function mpn_gcdext returns only s, not t, it
seems somewhat awkward to have to include the inequality for t in the
definition of what's a correct return value. I don't want to rule it
out, but it would be nice to have a simple inequality for s alone.
More information about the gmp-devel