Comment by logicallee
10 hours ago
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 three minutes on my phone.
[1] https://claude.ai/public/artifacts/baa198ed-5a17-4d04-8cef-7...
What are the false positive/negative rates?
for the way this one was done, this witness set has been proven to produce no false positives or negatives for n < 2³⁷.
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.