| ▲ | logicallee 9 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... |
|
| ▲ | amelius 6 hours ago | parent [-] |
| What are the false positive/negative rates? |
| |
| ▲ | logicallee 6 hours ago | parent [-] | | for the way this one was done, this witness set has been proven to produce no false positives or negatives for n < 2³⁷. | | |
| ▲ | _alternator_ 5 hours ago | parent [-] | | 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. |
|
|
