How To Prove That The Rijndael Polynomial Is Irreducible?

Question

I am learning about the AES algorithm which uses the finite field ${\mathbb{Z}_2[x]}\over{(p(x))}$, where $p(x)=x^8+x^4+x^3+x+1$.

How do you prove that this polynomial is irreducible? I know that for polynomials of degree $2$ & $3$ you could just check that it has no roots, but how would you do it for this polynomial?

Answer 1

In the case of a relatively low degree polynomial such as this one I would do it as follows. The task is to prove that a degree $d$ polynomial $p(x)$ is irreducible.

1. List all the irreducible polynomials of degrees $\le d/2$. Assume that the list looks like $p_1(x),p_2(x),\ldots, p_k(x)$.
2. Check that $p(x)$ is not divisible by any of the $p_i(x), i=1,\ldots,k$.

In the case $d=8$ the list of low degree polynomials looks like $p_1(x)=x$, $p_2(x)=x+1$, $p_3(x)=x^2+x+1$, $p_4(x)=x^3+x+1$, $p_5(x)=x^3+x^2+1$, $p_6(x)=x^4+x+1$, $p_7(x)=x^4+x^3+1$ and $p_8(x)=x^4+x^3+x^2+x+1$.

Note that you can build the necessary list of low degree candidates by applying the process recursively à la Sieve of Eratosthenes.

Also note that the above is the direct analogue of the primitive test for primality of an integer $n$. You check for divisibility by primes $p\le \sqrt n$. Here the "size" of the prime candidate is measured by its degree rather than its absolute value. In this sense checking for the presence/absence of zeros in the prime field is roughly equivalent to testing a prime candidate with divisibility by single digit primes. The analogy is between "the degree of a polynomial" and "the number of digits in the decimal expansion of an integer".

As in the case of prime number testing there are more efficient tests that are needed when a larger (w.r.t. the appropriate measure) candidate is checked out:

• As an analogue of Little Fermat based tests you can check that (over $\Bbb{F}_p$) you have $x^{p^d}\equiv x\pmod {p(x)}$ (and that this does not hold for any exponent $p^i, i<d$).
• There's the definitive test due to Berlekamp (see Bernard's answer).
• You can also run Berlekamp's factorization algorithm that is in a vague sense analogous to Rabin-Miller except it also does factorization rather than produces witnesses about irreducibility.

Answer 2

Use Berlekamp's algorithm. Actually, this algorithm gives more: it outputs afactorisation of polynomials over finite fields.

Let $\DeclareMathOperator\Fr{Fr}\Fr$ be the Frobenius homomorphism $\;u\longmapsto u^2$ on the $\mathbf Z_2$-algebra $\;\mathbf{Z}_2/(p(x))$. Then $p(x)$ is irreducible if $\;\dim\ker(\Fr-\operatorname{Id})=1$.

Consider the matrix $A$ of $\Fr-\operatorname{Id}$. This means you must check the $8\times8$ matrix $A$ has rank $7$.

Computation of the matrix of $\,\Fr$:

Its columns are the coordinates of (the classes of) $1, x^2, x^4,\dots,x^{14}$ in basis $(1,x,x^2,\dots,x^7)$.

For instance, we have \begin{align*}x^8&=x^4+x^3+x+1, \\ x^{12}&=x^8+x^7+x^5+x^4=x^7+x^5+x^3+x+1. \end{align*} Finally, you should obtain the matrix of $\Fr$: $$\begin{bmatrix} 1&0&0&0&1&0&1&0\\ 0&0&0&0&1&0&1&1\\ 0&1&0&0&0&1&0&1\\ 0&0&0&0&1&1&1&0\\ 0&0&1&0&1&0&0&1\\ 0&0&0&0&0&1&1&0\\ 0&0&0&1&0&1&0&0\\ 0&0&0&0&0&0&1&1\\ \end{bmatrix} $$ Another irredicibility test for polynomials over finite fields is the following:

Let $q$ be a prime power. A polynomial $f\in \mathbf F_q[x]$ of degree $n\ge1$ is irreducible if and only if:

(i) $f(x)$ divides $x^{q^n}-x$, and

(ii) for all prime divisors $d$ of $n$, $\;\gcd\bigl(x^{q^{n/d}}-x,f(x)\bigr)=1$

So in the present case, you should check the $p(x)$ divides $x^{256}-x$ and is coprime to $x^{128}-x$.

Reference:

Modern Computer Algebra, Joachim von zur Gathen & Jürgen Gerhard, Cambridge University Press (1999).