1
$\begingroup$

I know this question has been asked many times and there is good information out there which has clarified a lot for me but I still do not understand how the addition and multiplication tables for $GF(4)$ is constructed?

I'm just starting to learn about fields in general, galois fields and the concept of "it can't be 0 or 1 so it must be x"

I've seen; Galois Field GF(4); Addition and Multiplication in $F_4$; Explicit construction of a finite field with $8$ elements

but none explicity explain the construction and I'm too new to be told "its an extension of $GF(2)$"

Thank you in advance

$\endgroup$
8
  • 1
    $\begingroup$ I know you said you were too new, but do you understand how GF(4) $\cong \mathbb{F}_2[x]/(f(x))$ for some irreducible quadratic* polynomial $f(x)$? $\endgroup$
    – healynr
    May 5, 2020 at 23:10
  • 1
    $\begingroup$ If you are new to finite fields and don't want to study field theory, you can try viewing the addition of $GF(2^2)$ as $n$ copies of $GF(2)$ and filling the blanks in the multiplication table of $GF(4)$. Note that this method does not easily generalize to higher power. If you want to construct it through field extension, you probably need to study the nature of the polynomial ring over $GF(2)$ modulo an irreducible polynomial. Fortunately, matrices of form $\left(\begin{matrix}a&b\\b&a+b\end{matrix}\right)$ where $a,b\in GF(2)$ forms $GF(4)$. $\endgroup$ May 5, 2020 at 23:12
  • 1
    $\begingroup$ You are right about $\mathbb{F}_2[x]$. $\mathbb{F}_p$ just means field of order $p$ for some prime number $p$, of which there is only one up to isomorphism. When I write $(f(x))$, I am talking about the ideal generated by $f(x)$ (which is a prime, maximal ideal since $f(x)$ is irreducible). Basically, $\mathbb{F}_2[x]/(f(x))$ is a quotient ring that happens to be a field. Do you know what ideals and quotient rings are? $\endgroup$
    – healynr
    May 5, 2020 at 23:39
  • 1
    $\begingroup$ I wrote a long article about this exact question, that treats it in a completely synthetic way. If other explanations haven't helped for you, perhaps this one will: blog.plover.com/math/z2.html $\endgroup$
    – MJD
    May 6, 2020 at 0:19
  • 1
    $\begingroup$ There's only one way to fill it in. This is true for all the finite fields. $\endgroup$
    – user403337
    May 6, 2020 at 2:35

2 Answers 2

8
$\begingroup$

For any given $n$, there is at most one field with $n$ elements: only one, if $n$ is a power of a prime number ($2, 3, 2^2, 5, 7, 2^3, 3^2, 11, 13, \ldots$) and none otherwise ($6, 10, 12, 14\ldots$). This field with $n$ elements is written as $\Bbb F_n$ or as $GF(n)$.

Suppose we want to construct $\Bbb F_n$ where $n=p^k$. When $k=1$, this is easy-peasy: take the $n$ elements to be the integers $0, 1, 2\ldots p-1$, and the addition and multiplication are done modulo $n$.

When $k>1$ it is more interesting. One possible construction goes like this:

  1. The elements of $\Bbb F_{p^k}$ are the polynomials $$a_{k-1}x^{k-1} + a_{k-2}x^{k-2} + \ldots + a_1x+a_0$$ where the coefficients $a_i$ are elements of $\Bbb F_p$. That is, the coefficients are just integers in $\{0, 1, \ldots p-1\}$, but with the understanding that the addition and multiplication will be done modulo $p$. Note that there are $p^k$ of these polynomials in total.

  2. Addition of polynomials is done exactly as usual: combine like terms, but remember that the the coefficients are added modulo $p$ because they are elements of $\Bbb F_p$.

  3. Multiplication is more interesting:

    a. Pick an irreducible polynomial $P$ of degree $k$. “Irreducible” means that it does not factor into a product of smaller polynomials. How to actually locate an irreducible polynomial is an interesting question; here we will mostly ignore it.

    b. To multiply two elements, multiply them normally, remembering that the coefficients are in $\Bbb F_p$. Divide the product by $P$ and keep the remainder. Since $P$ has degree $k$, the remainder must have degree at most $k-1$, and this is your answer.


Now we will see an example: we will construct $\Bbb F_{2^2}$. Here $k=2$ and $p=2$. The elements will be polynomials of degree at most 1, with coefficients in $\Bbb F_2$. There are four elements: $0x+0, 0x+1, 1x+0, $ and $1x+1$. As usual we will write these as $0, 1, x, x+1$. This will not be misleading.

Addition is straightforward: combine like terms, remembering that $1+1=0$ because the coefficients are in $\Bbb F_2$:

$$\begin{array}{c|cccc} + & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 1 & x & x+1 \\ 1 & 1 & 0 & x+1 & x \\ x & x & x+1 & 0 & 1 \\ x+1 & x+1 & x & 1 & 0 \end{array} $$

The multiplication as always is more interesting. We need to find an irreducible polynomial $P$. It so happens that $P=x^2+x+1$ is the only one that works. (If you didn't know this, you could find out easily: a reducible polynomial of degree 2 factors into two linear factors. So the reducible polynomials are $x^2, x·(x+1) = x^2+x$, and $(x+1)^2 = x^2+2x+1 = x^2+1$. That leaves only $x^2+x+1$.)

To multiply two polynomials, we multiply them normally, then divide by $x^2+x+1$ and keep the remainder. For example, what is $(x+1)(x+1)$? It's $x^2+2x+1 = x^2 + 1$. There is a theorem from elementary algebra (the “division theorem”) that we can find a unique quotient $Q$ and remainder $R$, with the degree of $R$ less than 2, such that $PQ+R = x^2+1$. In this case, $Q=1, R=x$ works. (You should check this.) Since $R=x$ this is our answer: $(x+1)(x+1) = x$.

Let's try $x·x = x^2$. We want $PQ+R = x^2$, and it happens that $Q=1, R=x+1$ works. So $x·x = x+1$.

I strongly recommend that you calculate the multiplication table yourself. But here it is if you want to check:

$$\begin{array}{c|cccc} · & 0 & 1 & x & x+1 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & x & x+1 \\ x & 0 & x & x+1 & 1 \\ x+1 & 0 & x+1 & 1 & x \end{array} $$

To calculate the unique field $\Bbb F_{2^3}$ of order 8, you let the elements be the 8 second-degree polynomials $0, 1, x, \ldots, x^2+x, x^2+x+1$ and instead of reducing by $x^2+x+1$, you reduce by $x^3+x+1$. (Not by $x^3+x^2+x+1$, because that factors as $(x^2+1)(x+1)$.) To calculate the unique field $\Bbb F_{3^2}$ of order 27, you start with the 27 third-degree polynomials with coefficients in $\{0,1,2\}$, and you reduce by $x^3+2x+1$ (I think).


The special notation $\Bbb F_p[x]$ means the ring of all polynomials with coefficients from $\Bbb F_p$. $\langle P \rangle$ means the ring of all multiples of polynomial $P$. (A ring is a set with an addition, subtraction, and multiplication defined.)

When we write $\Bbb F_p[x] / \langle P\rangle$ we are constructing a thing called a “quotient” structure. This is a generalization of the process that turns the ordinary integers $\Bbb Z$ into the modular-arithmetic integers we have been calling $\Bbb F_p$. To construct $\Bbb F_p$, we start with $\Bbb Z$ and then agree that two elements of $\Bbb Z$ will be considered equivalent if they differ by a multiple of $p$.

To get $\Bbb F_p[x] / \langle P \rangle$ we start with $\Bbb F_p[x]$, and then agree that elements of $\Bbb F_p[x]$ will be considered equivalent if they differ by a multiple of $P$. The division theorem guarantees that of all the equivalent polynomials in a class, exactly one of them will have degree less than that of $P$, and that is the one we choose as a representative of its class and write into the multiplication table. This is what we are doing when we “divide by $P$ and keep the remainder”.


A particularly important example of this construction is $\Bbb R[x] / \langle x^2 + 1\rangle$. That is, we take the set of polynomials with real coefficients, but we consider two polynomials equivalent if they differ by a multiple of $x^2 + 1$. By the division theorem, each polynomial is then equivalent to some first-degree polynomial $ax+b$.

Let's multiply $$(ax+b)(cx+d).$$ As usual we obtain $$acx^2 + (ad+bc)x + bd.$$ From this we can subtract $ac(x^2 + 1)$ to obtain the equivalent first-degree polynomial $$(ad+bc) x + (bd-ac).$$

Now recall that in the complex numbers, $(b+ai)(d + ci) = (bd-ac) + (ad+bc)i$. We have just constructed the complex numbers,with the polynomial $x$ playing the role of $i$.

$\endgroup$
6
  • $\begingroup$ Absolutely brilliant! This took me from knowledge full of gaps to being able to explain it to somebody else now! Thank you! Can I just double check that $(x+1)(x+1)$ = $x^2+2x+1$ = $x^2+1$ as a consequence of Freshman's dream? $\endgroup$
    – K.M.
    May 6, 2020 at 14:32
  • 1
    $\begingroup$ I don't know what "freshman's dream" is. As it says higher up, “$1+1=0$ because the coefficients are in $\Bbb F_2$”. $\endgroup$
    – MJD
    May 6, 2020 at 14:45
  • 1
    $\begingroup$ I'm glad I could help. If you liked this article you might also like my blog article which approaches the same construction from a slightly different direction. It also contains an explicit construction of $\Bbb F_4$. $\endgroup$
    – MJD
    May 6, 2020 at 15:02
  • $\begingroup$ You might want to note that F_4 is the en.wikipedia.org/wiki/Eisenstein_integer s mod 2. This is, of course, because when you mod out x^2 + x + 1, you're saying it is 0, so x is a cube-root of unity. $\endgroup$
    – wnoise
    Aug 1, 2020 at 21:18
  • $\begingroup$ Very nice answer, but when I read this on your blog I thought it would be a nice explanation of how to pick the irreducible polynomial :( $\endgroup$ Aug 1, 2020 at 23:54
1
$\begingroup$

Well, take an irreducible polynomial of degree 2 over $GF(2)$. There is exactly one namely $f(x)=x^2+x+1$. Then the quotient ring $GF(2)[x]/\langle f(x)\rangle$ is a field, $GF(4)$, with 4 elements.

To construct the field, note that $f(x)$ has a zero in $GF(4)$ namely residue class $x+\langle f(x)\rangle$. Call it $\alpha$. Then $f(\alpha)=\alpha^2+\alpha+1=0$, i.e., $\alpha^2=\alpha+1$. Thus the elements of $GF(4)$ are $0,1,\alpha,\alpha^2=\alpha+1$. From here its simple to construct the addition and multiplication tables.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.