Cofactor canonicalisation of mpn_gcdext

Torbjorn Granlund tg at
Mon May 2 18:49:02 CEST 2011

nisse at (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 mailing list