AKS test for primes

AKS test for primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The AKS test for primes states that a number $p$ is prime 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 by the AKS test.

The task

1. Create a function/subroutine/method that given p generates the coefficients of the expanded polynomial representation of $(x-1)^{p}$.
2. Use the function to show here the polynomial expansions of p for p in the range 0 to at least 7, inclusive.
3. Use the previous function in creating another function that when given p returns whether p is prime using the AKS test.
4. Use your AKS test to generate a list of all primes under 35.
5. As a stretch goal, generate all primes under 50 (Needs greater than 31 bit integers).

Reference

• Fool-Proof Test for Primes - Numberphile (Video).