Is there an algorithm to find the splitting field of a polynomial over galois finite fields?

Question

how can I find the splitting field of polynomial $x^{13}+1$ over $GF(2)$?

Answer 1

Recall that:

1. Every irreducible polynomial over a finite field is separable

2. The field $GF(p^n)$ is the splitting field of $x^{p^n-1}-1$ over $GF(p)$.

In particular, for any separable polynomial $f(x) \in GF(p)[x]$ you have $$f(x) \mbox{ splits on } GF(p^n) \Leftrightarrow f(x) \mbox{ divides } x^{p^n-1}-1 $$

So an algorithm to find the splitting field of $f$ would be:

1. start with $n=1$.
2. compute $r(x)=x^{p^n-1}-1 \mod{f(x)}$ with the Euclidean algorithm.
3. if $r(x)=0$, the splitting field is $GF(p^n)$
4. otherwise, raise $n$ of one unity and go to step 2.

For your particular case, $x^{13}+1$ divides $x^{2^n-1}-1$ if and only if $13$ divides $2^n-1$: the smallest such $n$ is $12$ (because of Fermat's little theorem), hence the splitting field of $x^{13}+1$ over $GF(2)$ is $GF(2^{12})$.

Answer 2

Let $ P (X) = X ^ n-1 $, $ \Phi_n$ the n-cyclotomy polynomial over $ \Bbb{Q} $. Let $ p $ a prime number and $F_p$ the prime field of characteristic $ p $ and $ \Phi_ {n , F_p}$ the polynomial $ \Phi_n $ modulo $p$.

Link between $ \Phi_n $ and $ \Phi_ {n,F_p} $ :

Let $ d $ the order of $ p $ in the multiplicative group of units of the ring $ Z_n$, then $ \Phi_ {n, F_p} $ is the product in $F_p[X]$ of $ \frac {\varphi(n)}{d} $ irreducible factors of degree $d$.

Application:

The splitting field of $ X^{13} + 1 $ on $ F_2$ is the same as the splitting field of $ X^{13} -1$, so according to the above result knowing about the order of $p=2$ in $Z_{13}$ that is 12 equal to $\varphi(13)$ that $ \Phi_{n, f_p} = X^{12} + X^{11}+\cdot\cdot\cdot +X+1 $ is irreducible in $F_2 [X]$, and like any primitive root of this polynomial generates all others root of $ X^{13} + 1$ so, the splitting field is a cyclic extension of degree 12, is therefore $ F_{2^{12}} $.