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
I describe AKS in detail at my blog. I'm typing this on my phone so you will have to search for it yourself.