New code for primality testing

[Adrien Prost-Boucle]

Hi Marco,

> So, you have some possible implementation details in mind... If you want
> to read the code I pushed, and ask any question like "why did you
> implement this way that step?", I'll be happy to answer.

My approach was very modest in its design.
Mostly "use" existing mpz functions to reach a proof of concept,
rather than reaching a good adaptataion of gmp low-level stuff.
... and I only finished the Lucas-Lehmer test for Mersenne numbers xD

> > And I like your approach that keeps backward compatibility with better
> > perf.
> 
> It is intended for a GMP-6.2 release. For GMP-7 we should give different
> functions, I think.
> 
> > (even though the rationale about why reps-24 MR test becomes awkward)
> 
> There isn't any good reason for the number 24, I'm ready to change it, if
> other proposals arrive.

As a temporary compatilility implem it's OK.
It's for the long-term that I feel it's awkward in the API saying n-24
(whatever the constant value, 24 or anything else).

Would make a lot of sense to have one simple probable-prime test :
  int mpz_probab_prime_p (mpz_t n)

that explicitly does trial div + BPSW only.
This function would also be used as-is in nextprime().

And let the user launch additional MR tests in case he wants to increase primality probablility.
I mention MR tests, but that's just because it's already present in the code,
and because probabilities in the result are well known and studied.
Other better approaches may be possible. I just don't know others well.

> > Overall it would be great to extend the API with functions like these
> >   mpz_prime_mr_p(const mpz_t n, const mpz_t a)  // Miller-Rabin, just one
> 
> Easy to do, with a wrapper around the function millerrabin already
> available as an internal function in
> https://gmplib.org/repo/gmp/file/17707/mpz/millerrabin.c#l130
> 
> We can assume we will always have a Miller-Rabin implementation, so that
> we may decide to export it in the API....

Yes :-)

> >   mpz_prime_mr2_p(const mpz_t n, int reps)      // Miller-Rabin, perform
> > reps tests
> 
> It should also take a gmp_randstate_t parameter, and chose bases in the
> range [3..n/2]. But ... is this in the spirit of the API of the library?

I meant just the loop part of the function mpz_millerrabin (n, reps)
https://gmplib.org/repo/gmp/file/17707/mpz/millerrabin.c#l82
Maybe adding a randstate parameter following your suggestion (end of this message).

The BPSW part of that mpz_millerrabin() function would (should ?)
be moved to mpz_probab_prime_p() so the name mpz_millerrabin() keeps expected meaning.

But again, will we keep on having BPSW also in the future releases?
> Moreover... what is BPSW? Initial rial division or not? Up to which
> number? Strong or weak PSP tests? I'm not sure we should export it.

OK I can clean and clarify what I was said.

Anyone wanting to test primality would use, as first step ;
  int mpz_probab_prime_p (mpz_t n)
which would do current trial div + BPSW.

And in case more confidence is desired, launch more random MR tests :
  int mpz_millerrabin (mpz_t n, int reps)
which would NOT do trial div, just the loop part of current mpz_millerrabin().

> > And one or both like these for the fast Lucas-Lehmer test for Mersenne
> 
> I don't agree. The set of Mersenne's numbers is too small to write special
> code for it in a general library.
> I wrote a comment about Lucas-Lehmer, because Mersenne's number require a
> few special lines to be handled correctly...
> https://gmplib.org/repo/gmp/file/17707/mpz/lucmod.c#l57
> but I do not really thin it should be implemented.

Good point indeed :-)
As you also suggested, a demo program would be a more appropriate.

> >   - Future optimizations could consider AKR, APR, ECC tests
> 
> ...too complex for this library.
> Maybe the GMP-ECM [https://gforge.inria.fr/projects/ecm/] project already
> has the building blocks for Elliptic curve. GMP doesn't.
> 
> Some other free software projects already contain code for primality
> proving. E.g. Pari/GP [http://pari.math.u-bordeaux.fr/] implement both
> APR-CL and ECPP... I don't think GMP should duplicate that (good) work.

mpz_aprcl uses mpz already and is on a similar track about license
https://sourceforge.net/projects/mpzaprcl/

Thank you for the pointers on these projects.
It's just that, personal feeling maybe, there is a something "missing" from
the absence of deterministic primality test function (whatever the perf, to some extent).
But if it's too complex it's indeed a good reason.

> The probabilistic test should take a gmp_randstate_t parameter, so that
> repeated calls to the test can give increasing confidence.
> For this use-case we should also think about a way to skip the initial
> checks (trial division? BPSW?) for the second calls. A flag or different
> functions?

I'm OK for the randstate parameter.
No need to do initial checks / trial divs, these should have been done already
by a call to mpz_probab_prime_p().

Regards,
Adrien