mini-gmp mpz_powm incorrect result

[Marco Bodrato]

Ciao,
Il 2022-09-05 21:23 nisse at lysator.liu.se ha scritto:
> Marco Bodrato <bodrato at mail.dm.unipi.it> 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