Re: Likely GMP bug

[Marco Bodrato]

Ciao,

Il Sab, 26 Maggio 2018 11:01 pm, Niels Möller ha scritto:
> "Marco Bodrato"  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/

___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs

Re: Likely GMP bug

[Niels Möller]

"Marco Bodrato"  writes:

> Il Ven, 25 Maggio 2018 2:10 pm, Niels Möller ha scritto:
>> That fails with undefined behavior if by chance t == 2^31, so that c ==
>> 31.
>>
>> I don't see how that can happen, though, since ulimb, vlimb < 2^31
>> through out the loop, and t = (ulimb - vlimb) mod 2^32.
>
> ... but can jump inside the loop ...
>
> That's the culprit:
>
>   if (size > 1)
> {
>   ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
>   goto strip_u_maybe;
> }

Ah, that's subtle! Thank's for tracking it down. Do you know if it
results in a miscomputation on the typical (32-bit) machines where (x >>
32) == x?

> diff -r a2b594f11916 mpn/generic/gcd_1.c
> --- a/mpn/generic/gcd_1.c   Sun May 13 16:13:42 2018 +0200
> +++ b/mpn/generic/gcd_1.c   Sat May 26 09:29:41 2018 +0200
> @@ -83,8 +83,13 @@
> }
>
>ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
> -  if (ulimb == 0)
> -   goto done;
> +  ASSERT_ALWAYS (POW2_P (0));
> +  if (POW2_P (ulimb))
> +   {
> + if (ulimb != 0)
> +   vlimb = 1;
> + goto done;
> +   }
>
>goto strip_u_maybe;
>  }

Alternatively, change only the branch that have this problem,
something like this (untested):

*** /tmp/extdiff.B7tg0s/gmp.aab8a010d10f/mpn/generic/gcd_1.c
2018-05-26 10:42:48.367993924 +0200
--- /home/nisse/hack/gmp/mpn/generic/gcd_1.c2018-05-26
10:42:42.89642 +0200
*** mpn_gcd_1 (mp_srcptr up, mp_size_t size,
*** 180,185 
{
strip_u_maybe:
  vlimb >>= 1;
! t = ulimb;
}
count_trailing_zeros (c, t);
--- 180,189 
{
strip_u_maybe:
+ count_trailing_zeros (c, ulimb);
  vlimb >>= 1;
! ulimb >>= 1;
! /* c+1 is not always a valid shift count. */
! ulimb >>= c;
! continue;
}
count_trailing_zeros (c, t);

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