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}\)

Demo