mini-gmp: mpz_congruent_p and mpz_probab_prime_p

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> I changed the check_small function in the mini-gmp/tests/t-pprime_p.c file
> you just pushed to:
>
>   for (i = 0; i <  25005200; i++)
>     {
>       mpz_set_si (n, i);
>       check_one (n, isprime (i));
>     }
>
> It passed.

How long did that take? 

> 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?

If I understand this correctly, this implies that "early stop" doesn't
change the outcome (compared to an alternative implementation continuing
with additional more or less random bases in the correct range) for any
input arguments with reps <= 5000. Which is nice, and maybe should be
documented in some comment.

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

  if (reps > 25 && mpz_cmpabs_ui (n, 5000*5000+5000 + 41) < 0)
    reps = 25;
  else if (reps > 5000)
    reps = 5000;
 
and then delete the comparison mpz_cmp (y, nm1) >= 0), or replace it
with an assert. But that's not obviously making the code simpler.

Any better ideas?

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.