Talk:AKS test for primes

Combinations

There is a link between the coefficients of the expansion of $(x-1)^{p}$ and nCr. --Paddy3118 (talk) 20:56, 6 February 2014 (UTC)

Lower Limit

Again... 1 appears as an "is it prime, isn't it prime" candidate.

$1$ is prime if all the coefficients of the polynomial expansion of: $(x-1)^{p}-(x^{p}-1)$ are divisible by $p$. All the coefficients is the empty set. 1 is divisible by absolutely everything in the empty set. Is there a better wording out there? (That doesn't include the phrases "any number not 1" or "any number > 1") Tim-brown

It could also be worded that there isn't any number in the empty set that is divisible by $1$. I think 1 should simply be ignored Denommus

If you can "sweep it under the carpet" then why not? It is a small part of the task. --Paddy3118 (talk) 19:34, 7 February 2014 (UTC)

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…) –Donal Fellows (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 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, 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.

Hi, er, Danaj (please sign your talk page contributions using --~~~~).

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. --Paddy3118 (talk) 06:53, 21 February 2014 (UTC)