Re: mini-gmp mpz_powm incorrect result
Ciao, Il 2022-09-05 21:23 ni...@lysator.liu.se ha scritto: Marco Bodrato writes: 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. + if (mpz_cmp_ui (res, 1) <= 0) +mpz_add_ui (res, res, 9); Adding 9 looks very arbitrary? It is arbitrary. It is large enough to not be completely trivial and small enough to be short to write. I added a comment, saying that it is arbitrary :-) 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. The code handling e=0 is not so complex to deserve a sophisticated test. Anyway, of course the test can be improved. 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. Especially for _powm it is a good idea to return [1] for any x^0, regardless of x (i.e. also when x is 0). Otherwise, we should check whether x is 0 or not mod m. We just added the exception that the class [1] is represented by 0 when the modulus m=0. But that's not an exception wrt the above idea. Ĝis, m ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: mini-gmp mpz_powm incorrect result
Marco Bodrato 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. ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: mini-gmp mpz_powm incorrect result
Ciao,
Il 2022-08-30 10:25 Vincent Lefevre ha scritto:
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?
Concerning this second solution, the GMP manual says:
-- Function: int mpz_cmpabs_ui (const mpz_t OP1, unsigned long int
OP2)
Compare the absolute values of OP1 and OP2. Return a positive
value if abs(OP1) > abs(OP2), zero if abs(OP1) = abs(OP2), or a
negative value if abs(OP1) < abs(OP2).
So if the mpz_cmpabs_ui implementation is changed so that it can
return a value larger than 1, you need to make sure to remember to
update the code.
I propose to also add a couple of tests to mini-gmp/tests/t-powm.c , to
keep track of this.
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);
+
+ 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);
+ if (mpz_cmp_ui (res, 1) != 0)
+{
+ fprintf (stderr, "mpz_powm failed: b=m, e=0; 1 expected,\n");
+ dump ("m", res);
+ dump ("r", res);
+ abort ();
+}
+
+ /* Now res is 1. */
+ /* Test the case 1^0 (mod 1), expect 0. */
+ mpz_powm (res, res, e, res);
+ if (mpz_size (res))
+{
+ fprintf (stderr, "mpz_powm failed: b=1, e=0, m=1; 0
expected,\n");
+ dump ("r", res);
+ abort ();
+}
+
mpz_clear (b);
mpz_clear (e);
mpz_clear (m);
8<--
Ĝis,
m
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Re: mini-gmp mpz_powm incorrect result
Il 2022-09-05 19:04 Marco Bodrato ha scritto: Il 2022-08-30 10:25 Vincent Lefevre ha scritto: 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? I incorrectly removed the "Niels Möller wrote:" line. The question is for Niels, of course. I propose to also add a couple of tests to mini-gmp/tests/t-powm.c , to keep track of this. I'll push the tests just after the correction... Ĝis, m PS: thanks for the report ___ gmp-bugs mailing list gmp-bugs@gmplib.org https://gmplib.org/mailman/listinfo/gmp-bugs
Re: mini-gmp mpz_powm incorrect result
Paul Zimmermann writes:
> $ diff -u mini-gmp.c.orig mini-gmp.c
> --- mini-gmp.c.orig 2022-08-29 10:28:20.700995412 +0200
> +++ mini-gmp.c 2022-08-29 10:27:36.112191428 +0200
> @@ -3060,6 +3060,7 @@
>if (en == 0)
> {
>mpz_set_ui (r, 1);
> + mpz_tdiv_r (r, r, m);
>return;
> }
Should solve the problem, but maybe a bit overkill to call mpz_tdiv_r. Perhaps
mpz_set_ui (r, mpz_cmpabs_ui (m, 1) != 0);
or even (mn == 0 check just above this code rules out |m| < 1)
mpz_set_ui (r, mpz_cmpabs_ui (m, 1));
Regards,
/Niels
--
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Re: mini-gmp mpz_powm incorrect result
Thank you, I have confirmed that your patch resolves the issue.
On Mon, Aug 29, 2022 at 10:29 AM Paul Zimmermann
wrote:
> thank you, I confirm the bug, here is a potential fix:
>
> $ diff -u mini-gmp.c.orig mini-gmp.c
> --- mini-gmp.c.orig 2022-08-29 10:28:20.700995412 +0200
> +++ mini-gmp.c 2022-08-29 10:27:36.112191428 +0200
> @@ -3060,6 +3060,7 @@
>if (en == 0)
> {
>mpz_set_ui (r, 1);
> + mpz_tdiv_r (r, r, m);
>return;
> }
>
> Paul
>
> > From: Guido Vranken
> > Date: Sun, 28 Aug 2022 16:22:40 +0200
> >
> > The following program computes 1^0 % 1:
> >
> > //#include
> > #include "mini-gmp.c"
> > #include
> >
> > #define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }
> >
> > int main(void)
> > {
> > mpz_t a, b, c, res;
> > char* s = NULL;
> > /* noret */ mpz_init(a);
> > /* noret */ mpz_init(b);
> > /* noret */ mpz_init(c);
> > /* noret */ mpz_init(res);
> >
> > CF_CHECK_EQ(mpz_set_str(a, "1", 10), 0);
> > CF_CHECK_EQ(mpz_set_str(b, "0", 10), 0);
> > CF_CHECK_EQ(mpz_set_str(c, "1", 10), 0);
> > CF_CHECK_EQ(mpz_set_str(res, "0", 10), 0);
> >
> > /* noret */ mpz_powm(res, a, b, c);
> >
> > printf("%s\n", mpz_get_str(NULL, 10, res));
> > end:
> > return 0;
> > }
> >
> > The result should be 0, which is the case with regular libgmp, but with
> > mini-gmp the result is 1, and this is incorrect.
> >
> > Tested on version 6.2.1 and the latest repository checkout, with recent
> > clang and gcc, on x64 Linux.
> > ___
> > gmp-bugs mailing list
> > gmp-bugs@gmplib.org
> > https://gmplib.org/mailman/listinfo/gmp-bugs
>
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
Re: mini-gmp mpz_powm incorrect result
thank you, I confirm the bug, here is a potential fix:
$ diff -u mini-gmp.c.orig mini-gmp.c
--- mini-gmp.c.orig 2022-08-29 10:28:20.700995412 +0200
+++ mini-gmp.c 2022-08-29 10:27:36.112191428 +0200
@@ -3060,6 +3060,7 @@
if (en == 0)
{
mpz_set_ui (r, 1);
+ mpz_tdiv_r (r, r, m);
return;
}
Paul
> From: Guido Vranken
> Date: Sun, 28 Aug 2022 16:22:40 +0200
>
> The following program computes 1^0 % 1:
>
> //#include
> #include "mini-gmp.c"
> #include
>
> #define CF_CHECK_EQ(expr, res) if ( (expr) != (res) ) { goto end; }
>
> int main(void)
> {
> mpz_t a, b, c, res;
> char* s = NULL;
> /* noret */ mpz_init(a);
> /* noret */ mpz_init(b);
> /* noret */ mpz_init(c);
> /* noret */ mpz_init(res);
>
> CF_CHECK_EQ(mpz_set_str(a, "1", 10), 0);
> CF_CHECK_EQ(mpz_set_str(b, "0", 10), 0);
> CF_CHECK_EQ(mpz_set_str(c, "1", 10), 0);
> CF_CHECK_EQ(mpz_set_str(res, "0", 10), 0);
>
> /* noret */ mpz_powm(res, a, b, c);
>
> printf("%s\n", mpz_get_str(NULL, 10, res));
> end:
> return 0;
> }
>
> The result should be 0, which is the case with regular libgmp, but with
> mini-gmp the result is 1, and this is incorrect.
>
> Tested on version 6.2.1 and the latest repository checkout, with recent
> clang and gcc, on x64 Linux.
> ___
> gmp-bugs mailing list
> gmp-bugs@gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-bugs
___
gmp-bugs mailing list
gmp-bugs@gmplib.org
https://gmplib.org/mailman/listinfo/gmp-bugs
