find the degree of a minimal polynomial for a galois field element in an efficient way (by hand)

Question

I stumbled upon the following question in the problem section of a book on coding theory. A galois field $GF(2^4)$ is constructed as $K[x]$ modulo $1 + x^3 + x^4$ and $\beta$ is the class of $x$, so $1 + \beta^3 + \beta^4 = 0$. Moreover, $\beta$ is primitive and the table for its powers is:

0000 -
1000 1
0100 $\beta$
0010 $\beta^2$
0001 $\beta^3$
1001 $\beta^4$
1101 $\beta^5$
1111 $\beta^6$
1110 $\beta^7$
0111 $\beta^8$
1010 $\beta^9$
0101 $\beta^{10}$
1011 $\beta^{11}$
1100 $\beta^{12}$
0110 $\beta^{13}$
0011 $\beta^{14}$

The degree of the minimal polynomial $m_{\alpha}(x)$ for the element $\alpha$ = $\beta^6$ has to be found in an "efficient way". I'm not quite sure what is meant by that - finding the polynomial is listed as a separate problem.

Answer 1

Among those $16$ elements of $GF(2^4)$, $0$ and $1$ entered the picture in $GF(2)$, and with other two elements, $\beta^5$ and $\beta^{10}$, they constitute $GF(2^2)$ (as its multiplicative subgroup is cyclic of order $3$). All the other elements, including $\alpha=\beta^6$ must have degree $4$.

Anyway, $\alpha$ satisfies $\alpha^5=\beta^{30}=1$, and certainly $\alpha\ne 1$, so that $\alpha$ is the root of the cyclotomic polynomial $\displaystyle\frac{x^5-1}{x-1}=1+x+x^2+x^3+x^4$.

Answer 2

Maybe they expect you to use that the irreducible polynomial $m_{\alpha}(x)$ for $\alpha$ over ${\mathbb F}_2$ is $$ m_{\alpha}(x) = \prod_{k=0}^{n-1} (x-\alpha^{2^k}) $$ where $n$ is the smallest positive integer such that $\alpha^{2^n} = \alpha$. This result should be somewhere in your book.

You can check that $n=4$ by using that $\alpha = \beta^6$ and $\beta$ is primitive (and so has order 15). Hence the degree is 4, even though we haven't computed the polynomial yet.