sam-gram / aks Goto Github PK

This isn't the Agrawal–Kayal–Saxena test.

The AKS test uses the remainder polynomial from (x+a)^n / (x^r+a) so that at most you only have to look at r terms in the resulting remainder polynomial such that r grows at worst O(n(Log(n)^12)); whereas when you look at half of the binomial coefficients because you did the full (x+a)^n from Pascal's triangle your number of terms still grows exponentially to the number of digits in n.