Anonymous user
Talk:AKS test for primes: Difference between revisions
Found references to what they call "The AKS Test" in texts over 100 years old.
(Found references to what they call "The AKS Test" in texts over 100 years old.) |
|||
Line 23:
(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. Edit: This is theorems 75 and 76 of Hardy and Wright, which was in the 1975 version of the 4th edition, if not in earlier editions. It appears on page 58 of "The Elements of the theory of algebraic numbers" by L.W. Reid, 1910. Clearly it is not AKS.
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.▼
▲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 implementing the algorithm from the v6 paper. 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. [[User:Danaj|Danaj]] ([[User talk:Danaj|talk]]) 16:27, 21 February 2014 (UTC)
| |||