Likely GMP bug
bodrato at mail.dm.unipi.it
Sat May 26 22:09:54 UTC 2018
Il Sab, 26 Maggio 2018 11:01 pm, Niels Möller ha scritto:
> "Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:
> 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
> 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?
if limbs are unsigned long, and _ui functions can be used...
factor = 641; /* A factor of GMP_NUMB_MAX + 2 */
vlimb = factor * (GMP_NUMB_MAX / factor - 1);
ASSERT (vlimb > CNST_LIMB (1) << 31);
mpz_set_ui (U, vlimb);
mpz_mul_ui (U, U, somerandomdata);
mpz_add_ui (U, U, CNST_LIMB (1) << 31);
/* Try also sub_ui, because of MODEXACT */
> Yes. gcd (V, kV + 2^32) = gcd (V, 2^32) = 1. Not sure I see the
> connection to the bug, though.
I confused 32 with 31...
More information about the gmp-bugs