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