Cofactor canonicalisation of mpn_gcdext
Niels Möller
nisse at lysator.liu.se
Mon Nov 23 17:11:55 CET 2009
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
More information about the gmp-devel
mailing list