Cofactor canonicalisation of mpn_gcdext

[Torbjorn Granlund]

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.

-- 
Torbjörn