Cofactor canonicalisation of mpn_gcdext

[Torbjorn Granlund]

nisse at lysator.liu.se (Niels Möller) writes:

  Below an updated patch (also in my repository at shell), which seems to
  give the correct results and canonical cofactors. There's most likely a
  performance regression, due to the naive Euclid algorithm used in
  gcdext_1.
  
We can worry about later, either before GMP 4.4 get out of the door or
for GMP 4.5.

  There was one subtle problem left by the previous patch. After reducing
  numbers for a while, the gcdext code may find that the current two
  values are equal, and hence it has found the gcd and should return. But
  with which cofactor? Which of the two current cofactors is the canonical
  one depends on the reduction leading up to equality, which we don't keep
  track of. So in this case, we have to compare the two cofactors and
  return the smallest one.
  
Cute...

If you think this code is right, don't be shy: please push it into the
main repo and check http://gmplib.org/devel/testmachines.shtml tomorrow.

Bill and John, it would be very useful if you (since you caused all this
trouble...!) could test the code and check if it works as you wish.
Please confirm that it works in general, and also in for the discussed
"singularities".

Niels, how tight is the test code now?  If we agreed on leaving no
ambiguities (such as for gcd(u,u)) it would be useful if the testing
code would be as strict--that will help us when later optimising this
code.

We need to improve the doc/gmp.texi text.  (I could do that if I am told
the exact canonicalisation rules for the singularities.)

-- 
Torbjörn