New code for primality testing

Torbjörn Granlund tg at
Thu Nov 22 15:44:22 UTC 2018

nisse at (Niels Möller) writes:

  Would be fine with an algorithm that is unconditionally correct, but
  with a better bounds for the running time assuming unproven conjectures.

Sure, a Las Vegas algorithm, sort of.  IIRC, there is an algorithm which
runs in time O(n^4) assuming some for of Riemann Hypothesis, else in
non-polynomial time.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list