New code for primality testing

Torbjörn Granlund tg at
Wed Nov 21 15:33:34 UTC 2018

Paul Leyland <paul.leyland at> writes:

    I table of known exponents, and then just a lookup there?  Cute idea.
    For larger exponents, we might just execute a sleep(999999999) in an
    infinite loop as the computation will be too slow to terminate anyway.

  I note the smiley but you never know, someone might want to heat their
  house for a few years and then contribute a check result to GIMPS.

  (As for MR repeats mentioned in your other mail, I've long argued that
  running more than one test to a randomly chosen base is a complete
  waste of time.  If the test says it's composite, game over.  If it
  claims it may be prime you either want a slow deterministic proof or
  it is good enough for all practical purposes, including crypto.)

I agree 99%.

If the source of the random number is not under one's own control,
running more M-R rounds does make sense.  There exists numbers for which
1/4 of M-R bases are false prime witnessess.

But this is largely moot with BPSW, IIUC.

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list