Likely GMP bug

[Marco Bodrato]

Ciao,

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...

Ĝis,
m

-- 
http://bodrato.it/papers/