Anonymous user
Talk:AKS test for primes: Difference between revisions
→This isn't AKS: new section
(→Lower Limit: so it is an edge case) |
(→This isn't AKS: new section) |
||
Line 14:
: It would't be the first time a primality test has had some weird edge cases. (What about negative numbers? They'd need infinite polynomial expansions…) –[[User:Dkf|Donal Fellows]] ([[User talk:Dkf|talk]]) 21:55, 7 February 2014 (UTC)
== This isn't AKS ==
This seems like a corollary to Fermat's Little Theorem, not the AKS test:
(X+A)^N mod N = (X^N+A) mod N
(X-1)^N = X^N-1 mod N [set A=-1]
(X-1)^N - (X^n-1) = 0 mod N
The youtube video calls this the AKS test, but it has little resemblance to the v6 AKS algorithm. According to [http://en.wikipedia.org/wiki/Aks_primality_test#Concepts Wikipedia's AKS page], this method is exponential time. It is Lemma 2.1 from the v6 paper -- just the leading off point for starting the AKS theorems and algorithm.
The time growth for an AKS implementation should be ~3-4x longer for each 10x input size increase. Testing 99999989 should be somewhere in the range of 10 seconds for C code. This is of course all different by implementation, but this should give some clue.
An aside, I'm a bit confused by their talk, especially at the end, that "this is a fast test". It's ''ridiculously'' slow. Nobody uses this test in practice. It's very important in the theory, as it is deterministically polynomial time. But the constants are horrendously large. See, for example, [http://maths-people.anu.edu.au/~brent/pd/UMS10t4.pdf Brent 2010] "AKS is not a practical algorithm. ECPP is much faster." This includes run times of hundreds of years for numbers that ECPP does in a few seconds.
| |||