YomiK

4 ms·

1.
by YomiK 8y ago
"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
2.
by YomiK 9y ago
"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.
3.
by YomiK 9y ago
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.
4.
by YomiK 9y ago
You are correct. AKS (v6, Voloch, or Bernstein) is O(log^6(n)) with large constants. A nice polynomial but both large constants and a larger exponent than we'd like. APR-CL is O(log^K(n)) where K = C*log(log(log(n))), which means for
5.
by YomiK 9y ago
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 stringent than typical
6.
by YomiK 9y ago
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 RH w
7.
by YomiK 10y ago
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
8.
by YomiK 10y ago
There are many such formulas, such as Willan's 1964 simple formula for the nth prime. But they are basically all hiding a sieve, Wilson's theorem, the prime count function, or some other calculation. That is, none of them are at
9.
by YomiK 10y ago
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 in reason
10.
by YomiK 10y ago
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 relativel
11.
by YomiK 10y ago
It is a proven deterministic test of primality. We already had those before AKS, and they are significantly faster than AKS (even the various improvements). But they don't check all the boxes that are useful for stating things in com
12.
by YomiK 10y ago
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, this is not