4 ms·

there are also very fast primality tests that work statistically. It's called Miller-Rabin, I tested in the browser here[1] and it can do them all in about thr

• amelius 7mo ago
  What are the false positive/negative rates?
  • logicallee 7mo ago
    for the way this one was done, this witness set has been proven to produce no false positives or negatives for n < 2³⁷.
    • _alternator_ 7mo ago
      Nice. Notably with Miller-Rabin, you can also iterate the test cheaply and get exponentially low false positive/negative rates. I believe that this is how prime factors for RSA keys are usually chosen; choose an error rate below 2^-1000 and sleep extremely soundly knowing that the universe is more likely to evaporate in the next second than that you’ve got a false positive prime.