Some bugs

[danaj]

in phi(n), "return amount" is indented improperly, making phi(n) = 1 for all n.

in step3(n,r) the range is set to (r,2) instead of (2,r). This means the required trial division does not happen.

In both step3 and step5 you need to make sure your range includes the value.

In step5, um, what? You're setting x to an integer value and then just doing a modular exponentiation. That isn't how it works.

[benschlueter]

Thanks you.

1. Sure my mistake I correct it now.

2. I am not sure whats is wrong there? Edit: I got it I updated it 5 days ago and already fixed it 👍

3. x should be the base of a Polynomring. I thought 7 is the base of 2^3 (1+x+x^2+x^3).
   But I guess thats wrong.

Well I am not smart enough to get the math. So I've "try and error" and it worked (at least for all primes I've tested). I would appreciate if you correct the code or show me how to make step 5 right. And maybe there is a way to speed up step 2.

[danaj]

x is a variable that doesn't take a value. You need to compare two polynomials. All the operations are on the polynomial coefficients and exponents as we do polynomial math. The right side is easy as it is just 1*x^n + a, so the coefficients are 1 at exponent n (mod r), a at exponent 0, and 0 everywhere else. All the work is in expanding out (X+a)^n [the coefficients are all calculated mod n, the exponents mod r]. That is a completely different operation than just A^B mod C where all three are integers.

The problem with the "it worked for everything I tested" is that at that point we could just use BPSW. For over 30 years it has worked without fail for trillions upon trillions more numbers than you have tested, and is much faster than AKS, ECPP, APR-CL, etc. But we know it is not a proof, and there is a good argument as to why counterexamples should exist (but we do know now that the smallest one must be over 64 bits). Using AKS without doing it absolutely correctly doesn't make any sense to me.

[benschlueter]

Hmm but to implement it like this would cost much of compute power and I guess I am not smart enough to implement it with polynomial arithmetic .I have just a bit experience with finite field arithmetic.
But if I follow the wikipedia description, step5 looks like fermats little theorem for n = 31.

The only think I do not understand is why are there 2 numbers in the module bracket? (mod X^r − 1,n)

[https://en.wikipedia.org/wiki/AKS_primality_test]