mini-gmp mpz_powm incorrect result

Niels Möller nisse at lysator.liu.se
Mon Sep 5 21:23:07 CEST 2022


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

>>> or even (mn == 0 check just above this code rules out |m| < 1)
>>>
>>>    mpz_set_ui (r, mpz_cmpabs_ui (m, 1));
>
> I agree with this solution. Will you commit it?

Committed, and I've verified that it fixes Guido's test case.
 
> I propose to also add a couple of tests to mini-gmp/tests/t-powm.c ,
> to keep track of this.

Definitely needed, thanks for looking into that.

> ----8<------
> diff -r b0d6b9f5807e mini-gmp/tests/t-powm.c
> --- a/mini-gmp/tests/t-powm.c   Sat Aug 20 18:44:17 2022 +0200
> +++ b/mini-gmp/tests/t-powm.c   Mon Sep 05 19:02:23 2022 +0200
> @@ -53,6 +53,31 @@
>           abort ();
>         }
>      }
> +
> +  if (mpz_cmp_ui (res, 1) <= 0)
> +    mpz_add_ui (res, res, 9);

Adding 9 looks very arbitrary?

> +  mpz_set_ui (e, 0);
> +  /* Test the case m^0 (mod m), expect 1 (m is greater than 1). */
> +  mpz_powm (res, res, e, res);

Can we test mpz_powm (res, b, e, m), with e set to 0, and first |m| > 1,
then m = ±1? To get coverage for various signs and values for b and m.

BTW, it seems docs for mpz_powm doesn't say explicitly what 0^0 (mod m)
should give? But docs for mpz_*_pow_ui does say that 0^0 yields 1, so
for consitency, powm should give 1 mod m, which I think is what the code
(with fix) does.

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.


More information about the gmp-bugs mailing list