Cofactor canonicalisation of mpn_gcdext
Niels Möller
nisse at lysator.liu.se
Mon Nov 23 14:23:22 CET 2009
abbott <abbott at dima.unige.it> writes:
> I didn't know it either but it can be proved,
> see Theorem 4.3(vi) page 78 in Shoup's book:
> http://www.shoup.net/ntb/
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.
So equality, |t| = u / g or |s| = v/g, is not ruled out, as far as I
see. When does that happen, and which border is hit? When v/g is even,
one could choose between the ranges
-v/g <= 2s <= v/g - 2
and
-v/g + 2 <= 2s <= v/g
Which range does the values returned by Euclid's algorithm fit in?
Does it matter in the context of GMP?
For which inputs can we really require that 2 |s| < v/g, with *strict*
inequality?
Regards,
/Niels
More information about the gmp-devel
mailing list