How To Prove That The Rijndael Polynomial Is Irreducible? 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?
 A: 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).
A: 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.


*

*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)$.

*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.

