New code for primality testing
Torbjörn Granlund
tg at gmplib.org
Thu Nov 22 08:17:19 UTC 2018
"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:
Does this mean that we have to implement an unconditional primality
proving function to test if our "probab_primes" are really primes or they
are not?
A list of consecutive primes is better done with a sieve, of course.
Getting anywhere near 2^64 will still be too hard for our resources.
Assuming we can do 10^7 primes per second on the fastest GMP computer,
it's still a task which would take some 1500 years.
(We might want deterministic prime testing function, but I tend to think
that is outside the scope of GMP. If we anyway do that, should we
assume ERH? Then Artjuhov's O(n^4) algorithm would do. His algorithm
is the basis for Miller-Rabin. I don't think we'd achieve much by using
a deterministic algorithm which relies on an unproven theorem.)
--
Torbjörn
Please encrypt, key id 0xC8601622
More information about the gmp-devel
mailing list