# Find the first 4 elements of a given field

The polynomial $x^4 + x +1$ is unsplittable under $\mathbb{Z}_2$ .

Given the following $K$:

$K = \mathbb{Z}_2[x] / \mathbb{Z}_2[x] (x^4 + x +1)= {{a+bx+ cx^2 + dx^3 : a,b,c,d \in \mathbb{Z}_2}}$

I'm requested to find $4$ elements of sub-field of order $4$ of $K$.

The given $K$ is a field of order $16$. If $x^4 + x +1$ is unsplittable then I can't use it, I think (!??).

If so, do I need to find some other polynomial of order 4 and try to work with it ?

Something like $t^4 - t$ maybe ?

Regards

EDIT:

Sorry for the delay , I've some problems regarding the topic of finite fields . First , we work with the field of $Z_{2}$ , and we know that $t^4 = t$ , and also that :

$t^4 - t = t(t-1)(t^2 +t +1)$

As we can see , $t=0$ and $t=1$ are in the field , and now we're missing two more .

Now , assume that $t = a+bx+cx^2+dx^3$ , and place it in $t^2 +t +1$ , then : $(a+bx+cx^2+dx^3 )^2+a+bx+cx^2+dx^3+1 = a^2+b^2 x^2+c^2 x^4+d^2 x^6+(a+bx+cx^2+dx^3)==Break=$

Since $x^4=-x-1=x+1$ and $x^6=x^2⋅x^4=x^2(1+x)=x^2+x^3$

$==Continues=a+bx^2+cx^4+dx^6+a+bx+cx^2+dx^3+1=a+bx^2+c(x+1)+d(x^2+x^3 )+a+bx+cx^2+dx^3+1=$

{After a lot of arithmetics} $= x(b+c+d)+x^2 (b+c)+(c+d+1)⋅1$

Finally , if b=c=1 and d=0 , we'd get that :

$b+c+d=1+1+0=0$

$b+c=1+1=0$

$c+d+1=1+0+1=2=0$

Therefore the other two elements of this lovely field are : $1+x+x^2 ;x^2+x$

Since they are both closed for addition and multiplication :

Addition : $(x^2+x+1)+(x^2+x)=2x^2+2x+1=0+0+1=1$

Multiplication : $(x^2+x+1)(x^2+x)=x^4+x^3+x^3+x^2+x^2+x=x^4+2x^3+2x^2+1=x^4+0+0+x={x^4=x+1}=x+1+x=2x+1=0+1=1$

Now my questions are :

1. Is this correct ?

2. The addition and multiplication of the two , doesn't one of them supposed to give "0" zero ?

3. Why is it that $t^4 = t$ , always ?

Thanks !

-
You are asked to figure out the set of four combinations of $(a,b,c,d)$ such that the resulting set of elements of K is a subfield of $K$. Any subfield will contain the prime field, in this case $\mathbf{Z}_2$, so $0=0+0x+0x^2+0x^3$ and $1=1+0x+0x^2+0x^3$ are given. What about the other two? You need a little bit of theory. Have you constructed the field of 4 elements as an example in class? – Jyrki Lahtonen Mar 16 '12 at 5:13
No ,the lecturer just gave the rules and some theory regarding finite fields , but did not give any examples . I know how to construct fields , let's say 'build a field of order 9 , or of order 27' . – ron Mar 16 '12 at 5:17
The four roots of $t^4 - t$ in $K$ will indeed be a field of 4 elements, (this is a fact you know, right?) but you still need to find the roots.... Based on the way you asked the question, I feel like you haven't really wrapped your head around the question: it would be worth thinking over some more what you're given and what you're being asked to do. e.g. what did you have in mind by "using" or "working with" a polynomial? Try digesting Jyrki's comment and how it relates to the problem) – Hurkyl Mar 16 '12 at 5:21
@ron, ok. So what is your construction of the field of 4 elements? You adjoin an element satisfying a certain polynomial equation to the field $\mathbf{Z}_2$, right? Can you find such an element within this field? It is a lot of work to try them out in sequence, I know. What else do you know? Did you learn that the multiplicative group of a finite field is cyclic? It is possible to take advantage of that here! – Jyrki Lahtonen Mar 16 '12 at 5:24
Could it be that you're confusing the degree of a polynomial, the order of a group or field, and the order of an element? You write "some other polynomial of order $4$" and then give $t^4-t$ as an example. That's a polynomial of degree $4$. The (multiplicative) order of an element $a$ is the least integer $n$ such that $a^n=1$, and the order of a group or field is the number of its elements. – joriki Mar 16 '12 at 5:37

Further to Jyrki's comment that the multiplicative group of a finite field is cyclic: This means that you can write the $|K|-1=15$ non-zero elements as $a,a^2,\dotsc,a^{15}$, where $a$ is any of the $\phi(15)=8$ primitive elements of $K^*$. So an efficient strategy is to find the multiplicative order of some arbitrary element $a$ of $K$ other than $0$ and $1$; if it turns out to be $3$, you're done; if it turns out to be $5$, you know which $4$ elements to avoid on the second try; and if it turns out to be primitive, the multiplicative subgroup of order $3$ consists of $1=a^0,a^5$ and $a^{10}$. The easiest candidate to work with is $x$, and you can readily find that $x$, $x^2$, $x^3$, $x^4$, $x^5$ are all not $1$, so $x$ must be primitive (since otherwise its order would have to divide $15$ and thus be at most $5$). Thus the multiplicative subgroup of order $3$ consists of $1=x^0$, $x^5$ and $x^{10}$.

-
+1. On second thought we actually don't need cyclicity. $|K^*|=15$ and for the subfield $F$ we have $|F^*|=3$. So $|K^*/F^*|=5$. By Lagrange's theorem $a^5\in F^*$ for all $a\in K^*$. – Jyrki Lahtonen Mar 16 '12 at 7:42

It is true that the field of $p^k$ elements consists of the roots of the polynomial $t^{p^k}-t$ over $\mathbb{Z}_p$.

One nice consequence of this is that we can easily figure out all of the subfields of a finite field. The finite field of 16 elements, which you are working with, has two proper subfields-- the field of 4 elements and the field of 2 elements-- because $t^4-t$ and $t^2-t$ both divide $t^{16}-t$. (Note that it does not contain the field of 8 elements, since $t^8-t$ does not divide $t^{16}-t$.)

You already have a way to identify each of the 16 elements of $K$ in terms of $x$ (as as sum of the form $a+bx+cx^2+dx^3$); you just want specify which 4 elements form the subfield of order 4. (Two of them are obvious: $0=(0+0x+0x^2+0x^3)$ and $1=(1+0x+0x^2+0x^3)$.)

There are multiple ways to find the other two elements you need. (You could find the elements with the correct order under the Frobenius automorphism, if you know how to do so. Jyrki's excellent suggestion to think about the multiplicative order of the elements you want is probably the fastest way to solve the problem.) A direct, computational way is just to test which elements satisfy $t^4=t$, and to do this you will have to make use of the fact that $x$ is defined as satisfying $x^4+x+1=0$.

For example, to see if $u=(1+1x+0x^2+0x^3)$ is in the field of order 4, compute $u^4$ modulo 2: $$u^4 = (1+x)^4 = 1+x^4 = 1+(-x-1)= (0+1x+0x^2+0x^3) \neq u.$$ (Do you see how each step in the computation works?) Since $u^4 \neq u$, we know $u=(1+1x+0x^2+0x^3)$ is not in the field of order 4. (If you care to check, you will see that $u^{16}=u$, as it must.) You just have to find the other two elements that satisfy $t^4=t$.

1. Your work is correct; that's a nice way to find the elements you were looking for.

If you write $y=x^2+x$, then the four elements of the subfield are $0, 1, y,$ and $1+y$. (That is, they can be written as $a+by$ where $a,b \in \mathbb{Z}_2$.)
There is no reason to expect $(y) + (y+1)$ or $(y)(y+1)$ to equal $0$; we only require that taking sums and products of any elements from our subfield cannot equal anything outside the subfield. You can write out the full addition and multiplication tables for this field, if you want. As with any field, $uv=0$ only if $u=0$ or $v=0$; and $u+v=0$ only if $u=-v$.

3. It turns out that there are just a few possibilities for the structure of a finite field: $\mathbb{Z}_p$ where $p$ is prime or some finite extension of $\mathbb{Z}_p$. Further, any two fields of order $p^k$ are isomorphic, and their elements are just the roots of $t^{p^k}-t=0$.
These facts are not obvious; they must be proven. (You probably will prove them in class, or at least can find the proof in your book, but a sketch is below.)

For any finite field $K$, you can take its multiplicative identity $1$ and keep adding it until you get $1+1+ \ldots + 1 = 0$. The number of $1$'s in this sum will be a prime number $p$, and the subfield generated by $1$ has order $p$ and is isomorphic to $\mathbb{Z}_p$. Then $K$ is a vector space over this subfield, so it has order $p^n$ for some $n$.
The nonzero elements of $K$ form a multiplicative group of order $p^n-1$; thus by Lagrange's Theorem, they all satisfy $t^{p^n-1}=1$. Then all $p^n$ elements of $K$ satisfy $F(t)=t^{p^n}-t=0$. The equation $F(t)=0$ has at most $\text{deg}(F)=p^n$ distinct roots over any field; in the case of $K$, its roots are all $p^n$ elements of $K$. You can then show that $K$ is isomorphic to the splitting field of $t^{p^n}-t$ over $\mathbb{Z}_p$.

One more note about calculations in finite fields:

When you write the elements of a finite field as $a_1 + a_2 x + \ldots + a_n x^{n-1}$ with $a_i \in \mathbb{Z}_p$, addition is really easy to do, but multiplication takes more work, as you see. (You need to know the minimal polynomial of $x$; in this case it was $x^4+x+1=0$.) There's another way to write the elements of a finite field: as either $0$ or $\alpha^i$ where $0 \leq i < p^n-1$; with this system, multiplication is really easy, but addition takes more work. (You need to know the choice of generator $\alpha$ of the multiplicative group of the field.)

-
Okay that's nice , but why $u^4 = (1+x)^4$ ? where did the $(1+x)^4$ come from ? – ron Mar 16 '12 at 7:34
@ron: That's just because I'm doing the example $u=(1+1x+0x^2+0x^3)=1+x$. You should try other choices of $u$ to find the ones you want. – Jonas Kibelbek Mar 16 '12 at 7:37
I've made the calculations , I will edit my original post and I'd appreciate if you could check and give me some feedbacks ... I still have some problems however ,thanks – ron Mar 19 '12 at 15:58
@ron: Yes, please post your work; and I'll be glad to check it. – Jonas Kibelbek Mar 19 '12 at 17:16
@ron: Post another comment here when you've written out your calculations. That way I'll be notified and can come back here to look at them. – Jonas Kibelbek Mar 19 '12 at 17:53