0

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

James Waldby - jwpat7
  • 8,593
  • 2
  • 22
  • 37
antiloquax
  • 27
  • 1
  • 7
  • related: [AKS Primes algorithm in Python](http://stackoverflow.com/questions/347811/aks-primes-algorithm-in-python) – jfs Dec 26 '12 at 15:54
  • Well, first write something to computer `totient`. Then work out `square_root(totient(r) * log(n)`. Then, `for i in range(1, x)`, check whether the two values above are congruent (fast -- don't work them both out and then reduce!). Which bit of that do you have trouble with? – Katriel Dec 26 '12 at 16:17
  • Oh, thanks. X is a free variable, so do I test all X from 1 to a? – antiloquax Dec 26 '12 at 16:58
  • sqrt(totient(r) * log(n)) is wrong in that [wikipedia](http://en.wikipedia.org/wiki/AKS_primality_test#Algorithm) shows sqrt(totient(r)) * log(n) – James Waldby - jwpat7 Dec 26 '12 at 17:09
  • Thanks jwpat7. I didn't spot that. – antiloquax Dec 26 '12 at 17:20
  • @katrielalex I think you have prob. answered this I'll try coding that and see if it works. – antiloquax Dec 26 '12 at 17:24
  • For a fast&simple implementation I'd suggest you to look into the [`flint`](http://www.flintlib.org/) and write a small [C-extension](https://gist.github.com/4383382) to wrap polynomials with modular coefficients and big modulus. There is someone developing python bindings in Cython but until the end of october you couldn't use >2^64 modulus(and I don't know if he added support for this). Using numpy or scipy does not help much, since you'll have to deal with > 2^64 numbers. You may also look at [this](http://yves.gallot.pagesperso-orange.fr/src/aks.html)and try to translate from C++ to python – Bakuriu Dec 26 '12 at 21:57

1 Answers1

0

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

user448810
  • 17,381
  • 4
  • 34
  • 59