2
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ $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. $\endgroup$ Jan 28, 2019 at 1:59
  • $\begingroup$ @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. $\endgroup$
    – Khan Saab
    Jan 28, 2019 at 2:06
  • $\begingroup$ 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$. $\endgroup$ Jan 28, 2019 at 5:52
  • $\begingroup$ Eric Wofsey did explain the relevant bits in his answer. I simply elaborated. $\endgroup$ Jan 28, 2019 at 6:30

2 Answers 2

4
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jan 28, 2019 at 5:51
  • $\begingroup$ And +1 for including the interpretation $\beta=2$, $\beta+1=3$. I missed that in my first reading. $\endgroup$ Jan 28, 2019 at 6:15
4
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .