Cofactor canonicalisation of mpn_gcdext

[Niels Möller]

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
present confusion.

> 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.

Regards,
/Niels