The AKS algorithm for testing whether a number is prime is a polynomial-time test based on the following theorem: 

A number p is prime if and only if all the coefficients of the polynomial expansion of `(x − 1)^p − (x^p − 1)` are divisible by `p`.

For example, trying `p = 3`:

     (x − 1)^3 − (x^3 − 1) = (x^3 − 3x^2 + 3x − 1) − (x^3 − 1) = − 3x^2 + 3x 
    
And all the coefficients are divisible by 3, so 3 is prime.

Your task is to code the test function, wich will be given an integer and should return true or false based on the above theorem. You should efficiently calculate every coefficient one by one and stop when a coefficient is not divisible by p to avoid pointless calculations. The easiest way to calculate coefficients is to take advantage of binomial coefficients: http://en.wikipedia.org/wiki/Binomial_coefficient and pascal triangle: http://en.wikipedia.org/wiki/Pascal%27s_triangle . 

You should also take advantage of the symmetry of binomial coefficients. You can look at these kata: http://www.codewars.com/kata/pascals-triangle and http://www.codewars.com/kata/pascals-triangle-number-2

The kata here only use the simple theorem. The general AKS test is way more complex.  The simple approach is a good exercie but impractical. The general AKS test will be the subject of another kata as it is one of the best performing primality test algorithms.

The main problem of this algorithm is the big numbers emerging from binomial coefficients in the polynomial expansion. As usual Javascript reach its limit on big integer very fast. (This simple algorithm is far less performing than a trivial algorithm here). You can compare the results with those of this kata: http://www.codewars.com/kata/lucas-lehmer-test-for-mersenne-primes Here, javascript can barely treat numbers bigger than 50, python can treat M13 but not M17.

Difficulty: introductory

Starter code:

def aks_test(p):
	

Solutions:
def aks_test(p):
    lst = []
    for i in range(2, p+1):
        for j in lst:
            if i % j == 0:
                break
        else:
            lst.append(i)
    if p in lst:
        return True
    else:
        return False

import math
def aks_test(p):
    center = (math.factorial(p//2)*math.factorial(p-p//2))
    if center%p==0:
        return False
    return True

def aks_test(p):
    return p >= 2 and all(p % d != 0 for d in range(2, int(p ** 0.5) + 1))

P=[2]+[p for p in range(3,500000,2) if all(p%v for v in range(3,int(p**.5+1),2))]
S=set(P)

def aks_test(p):
    return p in S or p>2 and p&1 and all(p%v for v in P)

from math import factorial

def aks_test(p):
    if p in (1, 2): return p == 2
    
    f = p

    for k in range(1, 1 + p // 2):
        if f % p:
            return False
            
        f *= (p - k)
        f //= (k + 1)
            
    return True

def aks_test(n) :
    if (n <= 1) : 
        return False
    if (n <= 3) : 
        return True
    if (n % 2 == 0 or n % 3 == 0) : 
        return False
  
    i = 5
    while(i * i <= n) : 
        if (n % i == 0 or n % (i + 2) == 0) : 
            return False
        i = i + 6
  
    return True