New code for primality testing

[paul zimmermann]

       Ciao Marco,

> Someone published a sequence of 7 bases to deterministically test
> primality up to 2^64...
> But someone also claim that BPSW has no false positives up to 2^64...
> 
> If we can verify the source of the second claim, since we just implemented
> BPSW, we should decide to return 2 (surely prime) for all "probable"
> primes under this threshold.
> 
> By the way, I agree. In the API a generic function can take an unspecified
> reps parameter. On the other side, if we decide to expose a specific
> implementation (like MillerRabin), we should give to the users the full
> control on the parameters (the bases in this case).
> 
> A proposal for the function prototype? That could fit the need of GMP-ECM?

if you have already implemented BPSW, probaby the simplest is to make
mpz_probab_prime_p use BPSW (removing the reps argument), and have another
function mpz_millerrabin (mpz_t n, mpz_t base) and/or
mpz_millerrabin_ui (mpz_t n, unsigned long base).

As application, I was thinking more at CADO-NFS than GMP-ECM. In the
cofactorization phase of the Number Field Sieve, we have billions of
numbers of up to say 128 bits that we have to check for primality,
before trying to factor them.

Paul