Cofactor canonicalisation of mpn_gcdext

[Niels Möller]

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

> I'm attaching a patch addressing these first two points. For those with
> access to shell, it's also in the repository at ~nisse/hack/gmp-gcdext.

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.

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.

Regards,
/Niels

-------------- next part --------------
A non-text attachment was scrubbed...
Name: gcdext.patch
Type: text/x-patch
Size: 15543 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20091203/77e72647/attachment.bin>
-------------- next part --------------

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.