Likely GMP bug

[Niels Möller]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

> Thinking twice about this... I fear (x >> 32) == x is a problem.

I think so too. If we have ulimb = 2^31, the code wants to shift this
right 32 places and get zero. Which represents the odd value 1, since
the one bits are implicit. If we instead get ulimb = 2^31 after the
shift, that is interpreted as the odd value 2^32+1. This number has the
factorization 641 * 6700417, and if v happens to be a multiple of one of
these factors, and we will find that common factor and erroneously
return it as the gcd.

And we have potential miscpumputatino also on 64-bit, if we jump into
the code with ulimb = 2^63, and v has a common factor with 2^64+1 =
274177 * 67280421310721.

Is it possible to construct some examples with v a multiple of 641, and
input U such that ulimb = 2^31 after reduction?

> On the other side, if V is odd and U = kV + 2^32, then GCD(U,V)==1, right?

Yes. gcd (V, kV + 2^32) = gcd (V, 2^32) = 1. Not sure I see the
connection to the bug, though.

Regards,
/Niels

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