New code for primality testing

Marco Bodrato bodrato at
Wed Nov 21 20:50:06 UTC 2018

Ciao Paul,

Il Mer, 21 Novembre 2018 9:40 am, paul zimmermann ha scritto:
>> And it could be specified that this function
>>   int mpz_millerrabin (mpz_t n, int reps)

> in some contexts, we want to get a full primality test for moderate size
> numbers. For that purpose, it would be more useful to provide a list of
> (user chosen) bases to mpz_millerrabin, or at least that the bases chosen
> by a given 'reps' argument are documented.

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?



More information about the gmp-devel mailing list