Cofactor canonicalisation of mpn_gcdext
tg at gmplib.org
Mon May 2 18:49:02 CEST 2011
nisse at lysator.liu.se (Niels Möller) writes:
Maybe. If so, a similar note should be added to mpn_gcd (it also used to
destroy inputs plus an extra limb, right)?
Yes, please. :-)
> Perhaps mpz_gcdext (or some mpn_gcdext2) could perform an initial step
> (i.e., division) for this case, to avoid adding overhead to mpn_gcdext?
That was my first thought too, but it's not so easy, I'm afraid. Say U <
V, and we first divide
V = Q U + V'
Then call mpn_gcdext on U, V', so that
G = S' U + T' V' (where T' is implicit)
Then the needed cofactor is
S = S' - Q T' (an addition, since S' and T' have opposite signs)
So we'd still have to compute the implicit T' (which can be expected to
be of size roughly sn - qn),
I suppose I have to make some calculations to completely understand
this, so maybe what I say is simply dumb. I'd expect wanted S to be of
size vn (and the unwanted T to be of size un). Computing T' should
therefore not be too costly.
More information about the gmp-devel