# irreducible , extension field, coding

The following is a theorem I am trying to understand.

If $n$ is a positive integer and $m=2*3^{n-1}$
We know that $t^m+t^{m/2}+1$ is irreducible over GF(2).

I am looking at the case when $n=2, m=6$: so $f(t)=t^6+t^3+1$

Q1. What are the basic features of the corresponding extension field $F[\alpha]$ of F?

Since we are working in $GF$, $F[\alpha]$ has $(2^6)$ elements. But obviously $64-1$ ($F[\alpha ] \setminus \{0\}$) is not prime, so can't use Lagrange's theorem about primitive to calculate the order of $F[\alpha]$. How do I go about calculating that?

Q2. How do I expres $(1+\alpha)^{-1}$ as an F-linear combination of $1,\alpha,\alpha^2,...,\alpha^5$ ?

since $\alpha^6=\alpha^3+1$ here, solve $(1-\alpha)\sum(a_i\alpha^i)=1$

I get: $a_0 + a_5 = 1$
$a_0 + a_1 = 0$
$a_1 + a_2 = 0$
$a_2 + a_3 + a_5 = 0$
$a_3 + a_4 = 0$
$a_4 + a_5 = 0$

so $a_3=a_4=a_5=1$
and $a_0=a_1=a_2=0$

Can anyone go through my working and suggest things that can be improved, finished or missing? or even direct me to a book where i can read more about this ?

• I am reasonably sure you want $F[\alpha] \setminus \{0\}$ and not $F[\alpha]\{0}$...Do you want the latter unrenderable version?
– user21436
May 1, 2012 at 16:50
• In case you are wondering about the theorem itself, here's a proof I wrote as an answer to another question on this site. That is an exercise in Finite Fields by Lidl & Niederreiter - the tome of finite fields. May 1, 2012 at 17:14

Since $\alpha$ is a root of $t^6 + t^3 + 1$, that is, $\alpha^6 + \alpha^3 + 1 = 0$ and we are working in a field of characteristic $2$, we have $$\alpha^6 = \alpha^3 + 1 \Rightarrow \alpha^9 = \alpha^3(\alpha^3 + 1) = \alpha^6 + \alpha^3 = 1.$$ So, $\alpha$ is an element of order $9$ or a divisor thereof. But $\alpha$ cannot have order $3$ since $\alpha^3 = \alpha^6 + 1 \neq 1$ and so $\alpha$ has order $9$.

The standard way of solving problems of the type of Q2 is to use the extended Euclidean algorithm to express $1$, the gcd of $1+t$ and $t^6 + t^3 + 1$, as a linear combination of the two polynomials, that is, compute $a(t)$ and $b(t)$ of degrees less than $6$ such that $$a(t)(1+t) + b(t)(t^6 + t^3 + 1) = 1.$$ This is called Bezout's identity.

A mixture of hints and other bits.

Q1: Your first claim is correct. $F[\alpha]=GF(64)$. I assume that your question is about the order of $\alpha$. The big hint is that the irreducibility of $\phi(t)=t^6+t^3+1$ depends on the fact that $\phi(t)$ is a cyclotomic polynomial (at least the proof of irreducibility that I am thinking about depends on that piece of information). Which cyclotomic polynomial is it? What does that tell you about the order of its roots?

Q2:  Your solution looks good to me. Here's another way of going about it:[/Edit] $$1=\alpha^6+\alpha^3=\alpha^3(\alpha^3+1).$$ Can you write the right hand side in the form $(1+\alpha)$ times something?

• So $\alpha$ has order 9 ? May 1, 2012 at 16:57
• @KivEfehe: Correct. Well done! May 1, 2012 at 16:57
• Yay ! Not sure I know how to rewrite. $\alpha^3(\alpha^3+1)$. Why would this help?? May 1, 2012 at 17:05
• What I had in mind was: $(\alpha^3+1)=(\alpha+1)(\alpha^2+\alpha+1)$, so $$1=\alpha^3(\alpha^3+1)=(1+\alpha)(\alpha^3+\alpha^4+\alpha^5),$$ but the method of your solution is guaranteed to work, whereas this is just a trick :-) May 1, 2012 at 17:08
• Didn't you determine that $|F[\alpha]|=64$ at the beginning? What do you mean by 'order of $F[\alpha]$'?? I thought that was a misprint, and you wanted the order of $\alpha$. The order of a group is the number of its elements, and therefore the order of $F[\alpha]$ is 64. Somehow I think that you mean something else? May 1, 2012 at 18:17