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).

Python

<lang python>def expand_x_1(p):

   if p == 0: return [1]
   ex = [1, -1]
   for i in range(1, p):
       ex = [x - y for x,y in zip(ex+[0], [0]+ex)]
   return ex[::-1]

def aks_test(p):

   if p < 2: return False
   ex = expand_x_1(p)
   #if ex[0] != -1: return False
   ex[0] += 1
   return not any(mult % p for mult in ex[0:-1])
   
   

print('# p: (x-1)^p for small p') for p in range(12):

   print('%3i: %s' % (p, ' '.join('%+i%s' % (e, ('X^%i' % n) if n else )
                                  for n,e in enumerate(expand_x_1(p)))))

print('\n# small primes using the aks test') print([p for p in range(101) if aks_test(p)])</lang>

Output:

# p: (x-1)^p for small p
  0: +1
  1: -1 +1X^1
  2: +1 -2X^1 +1X^2
  3: -1 +3X^1 -3X^2 +1X^3
  4: +1 -4X^1 +6X^2 -4X^3 +1X^4
  5: -1 +5X^1 -10X^2 +10X^3 -5X^4 +1X^5
  6: +1 -6X^1 +15X^2 -20X^3 +15X^4 -6X^5 +1X^6
  7: -1 +7X^1 -21X^2 +35X^3 -35X^4 +21X^5 -7X^6 +1X^7
  8: +1 -8X^1 +28X^2 -56X^3 +70X^4 -56X^5 +28X^6 -8X^7 +1X^8
  9: -1 +9X^1 -36X^2 +84X^3 -126X^4 +126X^5 -84X^6 +36X^7 -9X^8 +1X^9
 10: +1 -10X^1 +45X^2 -120X^3 +210X^4 -252X^5 +210X^6 -120X^7 +45X^8 -10X^9 +1X^10
 11: -1 +11X^1 -55X^2 +165X^3 -330X^4 +462X^5 -462X^6 +330X^7 -165X^8 +55X^9 -11X^10 +1X^11

# small primes using the aks test
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]