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 Continue reading...
