Viewing profile — YomiK

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

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

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 …

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(lo…

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

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

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

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…

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…

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

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

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 …