5 ms·
M-R is a probabilistic primality test, with a deterministic variant for some ranges and a general-deterministic variant dependent on GRH. Lots of people want a
by web007 12y ago
M-R is a probabilistic primality test, with a deterministic variant for some ranges and a general-deterministic variant dependent on GRH. Lots of people want a better test, so we have Lucas-Lehmer and APRT-CL and AKS.
Better primality testing would be interesting to the crypto community, but it could rock the math world - like "Primes is in P" introducing AKS as the first deterministic polynomial time primality test.
As you said, though, better factoring would be game-changing for both cryptography AND mathematics.
- raiph 12y agoI've heard that, on modern cpus, with the first 100 or so primes cached, for all but the most performance sensitive applications, MR can be run with sufficient accuracy that there's a greater likelihood that a stray neutron will flip a bit in the cpu at the time of computing MR than that MR will produce an incorrect result. Or something like that. Is it true than MR can be tuned to be as useful as a non-probabilistic test?
- btilly 12y agoThis is absolutely true. Every time you run it, a non-prime has probability of at most 1/4 of passing. Run it 5 times, and you'll catch 99.9% of non-primes. What about neutron flips? Judging from http://lambda-diode.com/opinion/investigations/transmutations/.../ecc-memory-3 http://lambda-diode.com/opinion/investigations/transmutation... you can probably expect one every 4-5 years. If you run MR 20 times, your odds of wrongly declaring a non-prime prime are on the same order of magnitude as the number of microseconds in a 5 year period. So yes, neutron flips and MR errors are on par with each other. If you're concerned, just run MR a few more times. :-)