Search code examples
pythonprimes

polynomial section of the AKS algorithm in Python

I need a bit of help with the polynomial section of the AKS algorithm.

I have read quite a few descriptions online. I have got the perfect power test working and I think my get_r() function is correct. I am not sure how to go about doing this part of the algorithm:

For a = 1 to square-root(totient(r) * log(n)):
if (X+a)^n != X^n+a (mod X^r − 1,n), output composite

(Also see wikipedia article AKS primality test for a statement of the algorithm.)

Below are links to a program I wrote to implement the miller-rabin test and my (unfinished) aks code.

If someone can explain the maths or give me a bit of pseudocode, I should be okay. thanks

aks.py miller.py

Solution

  • I describe AKS in detail at my blog. I'm typing this on my phone so you will have to search for it yourself.