Cofactor canonicalisation of mpn_gcdext

[Niels Möller]

I wrote:

> It almost spells out the result we're talking about. Part (v) says, in
> our notation:
> 
>    |t| <= u / r_{\lambda-1}, |s| <= v / r_{\lambda-1}
> 
> where
> 
>   r_{\lambda-1} = r_\lambda q_\lambda = g q_\lambda
> 
> is the last-but-one nonzero remainder in the remainder sequence.

And one missing subtlety: We almost always have have q_\lambda >= 2,
which is how we get a factor of two. The only exception is the case u
= v, where we have only one quotient in the series, and the usual
strict inequality r_i > r_{i+1} is not satisfied.

So we have to exclude the cases where u = v, and we also have to
exclude the case v = 0 (this is also explicitly excluded in part (v)
of the theorem, we get no division at all, and the outputs aree g = u,
s = 1, t = 0 (or any arbitrary value), and even the most liberal of
our bounds, |s| <= v, is violated.

Excluding these cases, we have at least one division, and we have a
final quotient >= 2. When can get equality, 2|t| = u / g or 2|s| =
v/g?

Let me see if I can sort out the border cases. Assume that 2|s| = v/g.
Clearly both v/g and v are even. Then u/g must be odd. First, consider
s positive, then

  g = (v/2g) u + t v

or

  1 = (v/2g) (u/g + 2t)

This implies v = 2g and t = (g - u) / (2g).

So we must have the following sequence, for some k >= 1:

  r0 = (2k + 1) g    , s0 = 1, t0 = 0
  r1 = 2g            , s1 = 0, t1 = 1, q1 = k
  r2 = g = r0 - k r1 , s2 = 1, t1 = -k
  r3 = 0

The output is

  s = 1, v/g = 2,     with equality 2 |s| = v/g.
  t = -k, u/g = 2k+1, 2|t| = 2k < 2k+1 = u/g

For negative s, s = - v/2g, we get the same inputs and the
non-canonical representation s = -1, t = k+1,

  g = - (2k+1) g + (k+1) 2g

which will never be generated bu Euclid, and violates 2|t| <= u/g.

Next, assume t = v/2g. In a similar way, this implies the sequence

  r0 = 2g
  r1 = g

and cofactors s = 0 and t = 1, with equality 2 |t| = 2 = u/g.
And t = -v/2g leads to the alternative representation s = 1, t = - 1
which is not output by Euclid.

Summary:

We have strict inequality 2|s| < v/g and 2|t| < u/g whenever none of
the inputs equal the gcd or twice the gcd. And in the remaining cases
where we get equality, the offending s or t is 1.

This can also be expressed as

  - v/g < 2s < max(v/g, 3)
  - u/g < 2t < max(u/g, 3)
  

which should be valid in *all* cases.

Is this correect? Are these bounds suitable for the GMP interface?
Without thinking too deply, I think this requirement should determine
s and t uniquely, except when u = v in which case s = 1, t = 0 and s =
0, t = 1 are both allowed.

Regards,
/Niels