"Perhaps this work will finally prompt widespread change." I sure hope so. I've argued this to various languages and libraries for a few years, and mostly they don't really care, other than they've heard of M-R and not…
"not as slow as pre-AKS methods." only in terms of provable asymptotic bounds. It's much slower than APR-CL and ECPP, both of which existed before AKS, and are the methods used daily.
Pari/GP's APR-CL took 4 seconds to prove it. Perl's ntheory module took 2.6 seconds to prove with ECPP (including generating and verifying a certificate). That's over 1000x slower than BPSW but still not bad.
In typical use, primality testing for cryptography is probabilistic. Note that the testing one wants to do in an adversarial condition (where someone else, possibly nefarious, is giving you input) would be far more…
This is incorrect. "prime numbers would be too easy to find" -- they're already really easy to find. Factoring large semiprimes is currently hard. Primality testing and finding primes for RSA keys is very easy. If the…
Hart's OLF: http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S144678871200014... is an interesting variant. Like Caroline mentioned, you won't have any success with this on properly formed RSA keys, but Hart's OLF will very…
Not disagreeing, but I think both randomness and primality testing both have the problem that it's so easy to do them poorly. Generating random primes of these sizes isn't all that difficult, and even proofs can be done…
Could you elaborate on ECPP false negatives? A properly working ECPP should never give false negatives, e.g. return "prime" for a composite. Since ECPP can give a certificate unlike AKS or APR-CL, the caller could do a…
It's very clever, but obnoxiously slow. It's useful for code golf and as a pretty impressive party trick. But like your banker will not be impressed with your college funding plan of pulling a quarter out of his ear,…
"Perhaps this work will finally prompt widespread change." I sure hope so. I've argued this to various languages and libraries for a few years, and mostly they don't really care, other than they've heard of M-R and not…
"not as slow as pre-AKS methods." only in terms of provable asymptotic bounds. It's much slower than APR-CL and ECPP, both of which existed before AKS, and are the methods used daily.
Pari/GP's APR-CL took 4 seconds to prove it. Perl's ntheory module took 2.6 seconds to prove with ECPP (including generating and verifying a certificate). That's over 1000x slower than BPSW but still not bad.
In typical use, primality testing for cryptography is probabilistic. Note that the testing one wants to do in an adversarial condition (where someone else, possibly nefarious, is giving you input) would be far more…
This is incorrect. "prime numbers would be too easy to find" -- they're already really easy to find. Factoring large semiprimes is currently hard. Primality testing and finding primes for RSA keys is very easy. If the…
Hart's OLF: http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S144678871200014... is an interesting variant. Like Caroline mentioned, you won't have any success with this on properly formed RSA keys, but Hart's OLF will very…
Not disagreeing, but I think both randomness and primality testing both have the problem that it's so easy to do them poorly. Generating random primes of these sizes isn't all that difficult, and even proofs can be done…
Could you elaborate on ECPP false negatives? A properly working ECPP should never give false negatives, e.g. return "prime" for a composite. Since ECPP can give a certificate unlike AKS or APR-CL, the caller could do a…
It's very clever, but obnoxiously slow. It's useful for code golf and as a pretty impressive party trick. But like your banker will not be impressed with your college funding plan of pulling a quarter out of his ear,…