New code for primality testing
bodrato at mail.dm.unipi.it
Wed Nov 21 20:50:06 UTC 2018
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