# Find the elements of the extension field using primitive polynomial over $GF(4)$

Let $$p(z) = z^2 + z + 2$$ be a primitive polynomial. I want to construct the elements of the extensional field $$GF(4^2)= GF(16).$$

Since $$p(z)$$ is primitive polynomial , it should generate the elements of the extension field.

Let $$\alpha$$ be zero point then :

• $$\alpha^2 + \alpha + 2 \rightarrow \alpha^2 = -\alpha-2 \rightarrow \alpha^2 = 3\alpha + 2$$.

Using $$\alpha$$ :

• $$\alpha^1 = \alpha$$
• $$\alpha^2 = 3\alpha+2$$ and according to the book, $$\alpha^2 = \alpha+2$$ but $$-1 \mod 4 = 3$$.

Since the base is $$4$$ how can it be that the correct value of $$\alpha^2 = \alpha + 2$$?

I have mostly solved problems where the base is a prime number and the same procedure i have used here.

• $GF(4)$ is not the same as $\mathbb{Z}/(4)$; it's a degree $2$ extension of $\mathbb{Z}/(2)$. So over $GF(4)$, $z^2+z+2=z^2+z$ is not even irreducible. Jan 28, 2019 at 1:59
• @EricWofsey I want the coefficients to be one of the these values ${0,1,2,3}$. I need this for BCH codes where the coefficients are not only binary. Jan 28, 2019 at 2:06
• Khan Saab, see my answer for an explanation as to how $p(z)$ becomes a primitive polynomial. When we interpret the coefficient $2$ as a zero of $x^2+x+1$ in the field $GF(4)$, then $z^2+z+2$ is irreducible and also primitive. You need to adjust your meaning of $2$ for all this to make sense. Starting from $1+1\neq2$. Jan 28, 2019 at 5:52
• Eric Wofsey did explain the relevant bits in his answer. I simply elaborated. Jan 28, 2019 at 6:30

You seem confused about what $$GF(4)$$ is: it's not $$\mathbb{Z}/(4)$$ (which is not even a field). You can represent $$GF(4)$$ as an extension of $$GF(2)=\mathbb{Z}/(2)$$ by an element $$\beta$$ such that $$\beta^2=\beta+1$$. You can identify $$GF(4)$$ with the set $$\{0,1,2,3\}$$ by mapping $$\beta$$ to $$2$$ and $$\beta+1$$ to $$3$$, which appears to be what the book you refer to has in mind, but this does not mean you are working mod $$4$$ (the addition and multiplication operations are not ordinary mod $$4$$ addition and multiplication on $$\{0,1,2,3\}$$).

In particular, $$1+1=0$$ in $$GF(4)$$ and so $$\alpha+2$$ and $$-\alpha-2$$ are the same thing, and so you have $$\alpha^2=\alpha+2$$.

• You are correct about the confusion between $GF(4)$ and $\Bbb{Z}/(4)$. Yet, I'm sure the OP got their primitive polynomial from some source. See my answer for an explanation. Jan 28, 2019 at 5:51
• And +1 for including the interpretation $\beta=2$, $\beta+1=3$. I missed that in my first reading. Jan 28, 2019 at 6:15

Here is an educated guess. You are confused by the difference between algebraic/arithmetic and computers representation of elements of $$GF(4)$$.

The field $$GF(4)=\{0,1,\beta,\beta+1\},$$ where the arithmetic comes from the rules $$1+1=\beta+\beta=0$$, $$\beta^2=\beta+1$$. The element $$\beta$$ (it could be denoted by something else if you wish) has no integer naturally associated with it.

However, in computer implementations we (including code written by yours truly worth a couple hundred CPU hours) we write the elements of $$GF(4)$$ as string of two bits: $$0=00_2,\quad 1=01_2,\quad \beta=10_2,\quad \beta+1=11_2.$$ Do you see the idea? The element $$b_0+b_1\beta$$ is represented as the bitstring $$b_1b_0$$. Similarly we represent elements of $$GF(2^m)$$ as strings of $$m$$ bits. A big advantage of this is that addition in the field $$GF(2^m)$$ then becomes bitwise XOR of those bitstrings. Most (all?) computer hardwares have a superfast built-in function for performing bitwise XOR of two registers. So that's one of the basic arithmetic operations handed to us on a silver platter. Too good to pass up! The programmer only needs to worry about implementing the multiplication of $$GF(2^m)$$. For smallish values of $$m$$ there are efficient ways of doing that (Caveat: there are other ways of implementing e.g. $$GF(4^2)$$ even more efficiently for devices really short of memory).

Anyway, having fixed an internal presentation of elements of $$GF(2^m)$$, programmers occasionally refer to them as integers represented by the same string of bits.

Because the integer $$2$$ is $$10_2$$ in binary, such a programmer may choose to refer to $$\beta$$ as $$2$$ and $$\beta+1$$ as $$11_2=3$$. But they know that this is safe only among people in the know. If you do this in a general math forum, you are bound to confuse people. If you are a student still learning about this, you are bound to become confused by program documentation unless you first study this difference between algebraic notation and data representation internal to a computer.

So you may think of $$GF(4)$$ as the set $$\{0,1,2,3\}$$, but then you must include rules like $$1+1=0$$, $$2+2=0$$, $$3=2+1$$ in the definition of your addition. And, you also need to make rules like $$2*2=3$$, $$2*3=1$$ a part of your definition of multiplication. If you don't know this, you will be confused, and your questions will confuse others.

The above is all standard, but I claimed to have AN EDUCATED GUESS. Here it is.

If we present $$\beta=2$$ internally, then the quadratic $$p(x)=x^2+x+\beta "=" x^2+x+2$$ is a primitive polynomial. It takes a bit of experience to see this at a glance. But, see the last part of my linked answer (prepared with referrals like this in mind). You see that I explain there why $$x^2+x+\beta$$ is the minimal polynomial (over $$GF(4)$$) of some of the zeros of the well known primitive polynomial $$x^4+x+1$$ (over $$GF(2)$$).

So if $$\alpha$$ is a zero of $$p(x)$$ you can do the usual reduction business, and show that the elements $$\alpha^i, i=0,1,\ldots,14$$, are the non-zero elements of $$GF(16)$$, and $$\alpha^{15}=1$$: \begin{aligned} \alpha^2&=\alpha+\beta,\\ \alpha^3&=\alpha^2+\beta\alpha=(1+\beta)\alpha+\beta,\\ \alpha^4&=(1+\beta)\alpha^2+\beta\alpha=(1+\beta+\beta)\alpha+(1+\beta)\beta=\alpha+1,\\ \end{aligned} et cetera. All those powers of $$\alpha$$ can be written in the form $$c_1\alpha+c_0$$ where $$c_0,c_1$$ are elements of $$GF(4)$$. Feel free to continue that list. If we revert to the $$0,1,2,3$$ notation of elements of $$GF(4)$$, the above calculation presents $$\alpha^2$$ as $$\alpha+2$$, $$\alpha^3$$ as $$3\alpha+2$$ and $$\alpha^4$$ as $$\alpha+1$$. The last point proving that $$\alpha$$ is a zero of the primitive polynomial $$x^4+x+1$$ over $$GF(2)$$.