"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…
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…
"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…
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…