[tzs]

Just testing all the bases from 2 through 2 log(N)^2 doesn't actually seem to be too bad for N around 2^1024. It would be a little under 1007600 bases.

I've got a Miller-Rabin implementation in Python 3. Testing 2^1024 + 643, which is the first prime greater than 2^1024 with 65 random bases takes about 0.25 seconds on my Mac Studio. This is with no attempts at optimization or at using multiple cores.

At that rate testing 1007600 bases would take under 65 minutes.

Certainly way longer than you'd want to wait around for something like key generation, but if you didn't actually need your prime for an hour and really wanted to be certain it was a prime its not outrageous.

EDIT: I modified my Miller-Rabin to be the deterministic version, and made it take two parameters: cores and worker. I modified the loop that runs through the bases from 2 to floor(2 log(N)^2) to only actually test when "cores == 1 or base % cores == worker". I made my test program take cores and worker on the command line.

Then I ran this shell script, where prime.py is a program that checks 2^1024 + 643 for primality with the aforementioned deterministic Rabin-Miller:

  ./prime.py 8 0 &
  ./prime.py 8 1 &
  ./prime.py 8 2 &
  ./prime.py 8 3 &
  ./prime.py 8 4 &
  ./prime.py 8 5 &
  ./prime.py 8 6 &
  ./prime.py 8 7 &
  wait

Each of those 8 copies is testing a different 1/8th of the bases that need to be tested. My computer has 8 performance cores and the hope was that MacOS would run each on a different core. That did seem to be the case.

It took 392 seconds for them all to complete, with each correctly reporting that 2^1024 + 643 has passed for all their bases.

[lifthrasiir]

> Just testing all the bases from 2 through 2 log(N)^2 doesn't actually seem to be too bad for N around 2^1024. It would be a little under 1007600 bases.

Unfortunately this limit depends on the currently unproven conjecture (a subset of the generalized Riemann hypothesis). You have to check all n bases to be unconditionally correct.

[djao]

Going up to n is surely excessive. You need a version of the Riemann hypothesis to get any sort of logarithmic bound, but a sqrt(n) bound can be achieved using unconditional Polya-Vinogradov type inequalities. (A successful Miller-Rabin test corresponds to a nontrivial value of a Dirichlet character, and Polya-Vinogradov ensures that the least such value cannot exceed sqrt(n) * ln(n), unconditionally without the need for any Riemann hypothesis.)

A reference for this material is "Explicit bounds for primality testing and related problems" by Eric Bach, Math. Comp. 55 (191), July 1990, pp. 355-380.

[pbsd]

The best asymptotic bound is somewhere between n^(1/8sqrt(e) + eps) and n^(1/6.568sqrt(e) + eps), per [1].

[1] https://doi.org/10.1007/BFb0030409

[pbsd]

You only need to try the _prime_ bases up to 2 log^2(n). So the total number of bases here would be 79060.

[tzs]

Here is prime.py if anyone wants to play around with it: https://pastebin.com/FFw4qrvU