"Marco Bodrato" <bodr...@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. _______________________________________________ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs