Anonymous user
Talk:AKS test for primes: Difference between revisions
→This isn't AKS
(Add signature to previous comment (doh!)) |
|||
Line 35:
:: As for the real version of AKS, the state of the theory advanced very far in the years following the AKS paper. The original version was polynomial time but too slow to use on any kind of reasonable numbers. Now the state-of-the-art "AKS-class test" (as these are being called) is almost competitive with ECPP. It's still true that no one uses this test in practice, but if someone spent the time to write an optimized implementation using the lowest heuristic exponent (slightly more than 4) and Bernstein's improvements on the constant factor, it should only a few times slower.
:: [[User:CRGreathouse|CRGreathouse]] ([[User talk:CRGreathouse|talk]]) 14:34, 21 February 2014 (UTC)
::: I think the task itself is great for RC. My complaints are (1) calling it AKS (read the paper), and (2) perpetuating the idea that this is a current practical speed breakthrough.
::: CRGreathouse is correct that there have been huge improvements since the first paper. Importantly, someone else may come up with another insight that further improves the performance. We haven't even seen a good implementation of the improvements from Bernstein's 2006 paper (that I'm aware of).
:::Brent's implementation in the 2010 presentation I referenced includes Lenstra and at least one of Bernstein's improvements (it looks like this is not the 2006 k=4 randomized algorithm nor the additional improvements Bernstein's 2002 paper mentions, but just his first ''s/r'' reduction plus Lenstra's improvement), and still gets quite long times. Bornemann's 2002 Pari implementation uses the Lentra, Voloch, and Bernstein improvements, and is quite small and runs much faster than many others, but is still pretty far off APR-CL / ECPP. Going to the best "AKS-class" algorithm plus basic improvements would seem like it could be competitive. I don't think those fastest versions are deterministic however (unlikely to matter in practice).
::: [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 18:10, 21 February 2014 (UTC)
| |||