Anonymous user
Talk:AKS test for primes: Difference between revisions
→This isn't AKS: agreed
(→This isn't AKS: Tell numberphile please.) |
(→This isn't AKS: agreed) |
||
Line 32:
:Hi, er, Danaj (please sign your talk page contributions using <nowiki>--~~~~</nowiki>).
:I guess this is the AKS test according to numberphile at the moment. It was the easy suitability of the explanation in forming an RC task that made me create it; I only added the other link afterwards. If you get numberphile to retract then I would be glad to change the task name. --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 06:53, 21 February 2014 (UTC)
:: Danaj is correct -- this isn't AKS, and it isn't fast. My entry has a 'fast' version of this task which uses modular reductions but even that isn't fast at all.
:: 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)
| |||