mini-gmp: mpz_congruent_p and mpz_probab_prime_p

[bodrato at mail.dm.unipi.it]

Ciao,

Il Mer, 12 Marzo 2014 11:08 am, Niels Möller ha scritto:
> bodrato at mail.dm.unipi.it writes:
>
>> I changed the check_small function in the mini-gmp/tests/t-pprime_p.c

>>   for (i = 0; i <  25005200; i++)

> How long did that take?

I didn't measure... maybe ten minutes?

>> This means that all composites smaller than 5000*5000+5000+41 are
>> detected
>> within the first 25 reps.
>> Any number outside the interval I tested will not trigger the
>>   if (mpz_cmp (y, nm1) >= 0)
>> branch if the reps argument is >5000...
>
> I guess a negation is missing there? The condition can be true only if
> reps > 5000?

Yes, a negation... or consider "<5000".

The idea is: if reps <= 5000, the "(mpz_cmp (y, nm1) >= 0)" condition is
triggered only for primes. So that the result is the expected one.

Since using reps > 5000 is obviously a nonsense (if you can wait so much
time, probably a deterministic primality-proving algorithm is better :-),
if a user set the parameter to such a big number of repetitions, he
deserves any possible misrepresentation of a composite as a "probable
prime" due to that branch :-)

> But does it open any posibilities for making the code simpler? I guess
> one could add some clipping of the reps argument, like

No, I don't think so.

> Any better ideas?

The code is simple now, we can maybe move the branch outside of the loop,
but this does not simplify the code. And the cost of the comparison is
negligible wrt powm.

Regards,
m

-- 
http://bodrato.it/