AKS Primality test notes
The extended Fermat’s Little theorem
$$\begin{align*} &\text{Let } a \in \mathbb Z, n \in \mathbb N, n \ge 2, (a,n)=1 \text{ then:} \\ &(x+a)^n \equiv x^n + a (\mod n) \text{ if and only if } n \text{ is a prime number} \end{align*}$$
We'll prove this in two parts:
Part 1: If $n$ is prime, then \((x+a)^n \equiv x^n + a (\mod n)\)
$$\begin{align*} (x+a)^n - (x^n + a) &= x^n + \binom{n}{1}x^{n-1}a + \binom{n}{2}x^{n-2}a^2 + \dots + \binom{n}{n-11}xa^{n-1} + a^n - (x^n + a) \\ &=\binom{n}{1}x^{n-1}a + \binom{n}{2}x^{n-2}a^2 + \dots + \binom{n}{n-11}xa^{n-1} + (a^n - a) \end{align*}$$
Since $n$ is a prime number, according to Fermat’s Little Theorem \(a^n \equiv a (\mod n) \implies n |(a^n - a)\). Moreover, all coefficients \(\binom{n}{k} = \frac{n!}{(n-k)!k!}\) are divisible by $n$. This is because $n$ is a factor in the numerator $n!$ but not in the denominator \((n-k)!k!\). Therefore, if $n$ is a prime number then \((x+a)^n \equiv x^n + a (\mod n)\)
Part 2: If \((x+a)^n \equiv x^n + a (\mod n)\) then $n$ is prime.
We will proof by contradiction: If $n$ is composite, let $q $ be a prime factore of \(n, q^k|n\). Looking at the coeffiient \(\binom n q x^q a^{n-q}\):
\(\binom n q\)is not divisible by \(q^k\)
\(a^{n-q}\) coprime with \(q^k\)
So \(\binom n q a^{n-q}\) is not divisible by $n$ for all $a, x$ (contradiction!). Therefore $n$ must be prime.
Conclusion:
We've shown both directions of the if and only if statement, thus proving that:
$$\begin{align*} &\text{Let } a \in \mathbb Z, n \in \mathbb N, n \ge 2, (a,n)=1 \text{ then:} \\ &(x+a)^n \equiv x^n + a (\mod n) \text{ if and only if } n \text{ is a prime number} \end{align*}$$
The main idea
The above theorem suggests another primality test: given $n$ as input, chose an $a$ and test whether the theorem above holds for $n$. However, this requires $O(n)$ since we need to calculate \(n+1\) coefficients of \((x+a)^n\). In order to reduce the number of coefficients, we calculate the remainder of the division of the polynomials of the theorem by a polynomial in the form of \(x^r - 1\), for an appropriately chosen small $r$. In other words, we test:
$$(x+a)^n \equiv x^n + a (\bmod x^r-1, n)$$
How to reduce the calculation of \(n+1\) coeficients
One may say that, in order to calculate \((x+a)^n \bmod (x^r-1)\) still have to calculate all \(n+1\) coefficients of \((x+a)^n\), hoever, we can avoid this by continuously performing modulo and square the remainders. For example:
$$\begin{align*} (x+1)^5 \bmod (x^2-1) &= (x+1)(x+1)^4 \bmod (x^2-1) \\ &= (\underbrace{(x+1) \bmod (x^2-1)}{x+1})(\underbrace{((x+1)^2)^2}{(x+1)^4} \bmod (x^2-1)) \\ &=(x+1)(\underbrace{(x+1)^2 \bmod (x^2-1)}{2x+2})^2 \\ &=(x+1)(\underbrace{(2x+2)^2 \bmod (x^2-1)}{8x+8}) \\ &=(x+1)(8x+8) \bmod (x^2-1) = 16x+6 \end{align*}$$
The point of doing this is if $r$ is not too large, the polynomial \((x+a)^n\) can be reduced to be the degree less than $r$, thus, the complexity becomes less than $O(n)$. If \(r=O(\log^{O(1)}n)\), then one can test in time \(O(\log^{O(1)} n)\). This is the most important part to understand the paper.
Calculate \(x^n+a \bmod x^r-1\)
One can easily calculate this in $O(1)$ by:
$$x^n+a \bmod x^r-1 = \begin{cases} a+1, \quad \text{ if } r|n \\ x^{n \bmod r} + a, \quad \text{ otherwise} \end{cases}$$
Example: \(x^5+3 \bmod x^3 - 1 = x^2+3\), and \(x^4 + 2 \bmod x^2-1 = 3\)
You can eassily prove this by yourself.
For the rest sections, I won’t show the prove since they’re proven quite clear in the paper. I will just note the main ideas only.
The AKS Theorem (key theorem)
Now the problem is there might be some composites that satisfies \((x+a)^n \equiv x^n + a (x^r-1, \bmod n)\), but not \((x+a)^n \equiv x^n + a (\bmod n)\) However, for an appropriate chosen $r$, if the equation is satisfied for several $a$’s then $n$ must be prime power.
We have this in the key theorem of the paper, dictated from the main algorithm:
Given \(r: (r,n) = 1\) such that \(o_r(n) \gt \log^2n\), with \(o_r(n)\) is the order of mulpliticative \((\mathbb Z / r \mathbb Z)^{\times}\). Assume that for all $a$’s such that: \(1\le a \le O(r\log n)\) and satisfies \((x+a)^n \equiv x^n + a (x^r - 1,\bmod n)\) then $n$ is either a prime or a power of a prime.
The existence of good $r$
From the beginning until now, we have gone through the main ideas of the article in turn:
Use polynomials for primality checking
Reduce the polynomial degree by modulo by \(x^r - 1\)
Prioven that there are some $r$ and \(1\le a \le O(r\log n)\) always satisfies \((x+a)^n \equiv x^n + a (x^r-1, \bmod n)\) then $n$ is either a prime or a power of a prime.
Now, prove the last thing: $r$ exists via Lemma 3:
There exists \(r=O(\log^{O(1)}n)\) coprime to $n$, such that $n$ has order greater than \(\log_2^2n\) in \((\mathbb Z/r\mathbb Z)^{\times}\)