AKS primality test
The algorithm

The algorithm is as follows:

Here ord (n) is the multiplicative order of n modulo r, log is the binary logarithm, and φ (r) {\displaystyle \varphi (r)} is Euler's totient function of r.

Step 3 is shown in the paper as checking 1 < (a, n) < n for all a ≤ r. It can be seen this is equivalent to trial division up to r, which can be done very efficiently without using gcd. Similarly the comparison in step 4 can be replaced by having the trial division return prime once it has checked all values up to and including ⌊ n ⌋. {\displaystyle \left\lfloor {\sqrt {n}}\right\rfloor.}

Once beyond very small inputs, step 5 dominates the time taken. The essential reduction in complexity (from exponential to polynomial) is achieved by performing all calculations in the finite ring

consisting of n r {\displaystyle n^{r}} elements. This ring contains only the r {\displaystyle r} monomials { X 0, X 1, …, X r − 1 } {\displaystyle \{X^{0},X^{1},\ldots,X^{r-1}\}}, and the coefficients are in Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } which has n {\displaystyle n} elements, all of them codable within log 2 (n) {\displaystyle \log _{2}(n)} bits.

Most later improvements made to the algorithm have concentrated on reducing the size of r, which makes the core operation in step 5 faster, and in reducing the size of s, the number of loops performed in step 5. Typically these changes do not change the computational complexity, but can lead to many orders of magnitude less time taken; for example, Bernstein's final version has a theoretical speedup by a factor of over 2 million.
startend:end_checker