5.3 Galois Fields

Finite (Galois) Fields

A Galois field, also known as a finite field, is a set of elements equipped with arithmetic operations, such that the result of any operation is always an element of the set.

More particularly, a finite field with $p$ elements is denoted ${\mathbb{F}}_p$ or $\mathrm{GF}(p)$, where $p$ is a prime number or a power of a prime. In the case where $p$ is prime, the field consists of the integers
$\{0,1,2,\dots ,m-1\},$
with all arithmetic performed modulo $m$.

The number of polynomials of degree at most $d$ over a finite field ${\mathbb{F}}_m$ is $m^{d+1}$, since there are m choices for each of the $d+1$ coefficients. When specifying a polynomial by values at $d+1$ distinct points, there are also $m^{d+1}$ possibilities.

Intuition

The defining feature of a Galois field is that it contains only a finite number of elements, yet all standard arithmetic operations are still valid. This structure allows for consistent algebraic manipulation in settings where only a limited number of values are available, such as polynomial arithmetic modulo a prime.

Properties

(Counting Theorem) The number of polynomials of degree at most $d$ over a finite field ${\mathbb{F}}_p$ is $p^{d+1}$.

Examples

(Medium) Polynomial Arithmetic Over a Finite Field

Let $f(x)=3x^2+5x+2$ and $g(x)=x+4$, such that both polynomials are in ${\mathbb{F}}_7$.

Evaluate $f(0),f(1),f(2),f(3)$. We have $f(0)=2$, $f(1)=10\equiv 3(\mathrm{mod}7)$, $f(2)=24\equiv 3(\mathrm{mod}7)$, $f(3)=44\equiv 2(\mathrm{mod}7)$.

Compute $h(x)=(f\cdot g)(x)$. What is $h(6)$? We have that $(f\cdot g)(x)=3x^3+17x^2+22x+8\equiv 3x^3+3x^2+x+1$.

Then, $h(6)=3\cdot 6\cdot 36+3\cdot 36+7\equiv 4\cdot 1+3\cdot 1+0\equiv 7\equiv 0(\mathrm{mod}7)$. Therefore, $h(6)=0$ in ${\mathbb{F}}_7$.

Now, let $f$ and $g$ be some polynomials in ${\mathbb{F}}_p$.

We say a polynomial $f=0$ if $\forall x,f(x)=0$. Show that if $f\cdot g=0$, it is not always true that either $f=0$ or $g=0$. Let's work over $F_2$. Then, let $f(x)=x$ and $g(x)=x+1$. Then, $(f\cdot g)(x)=x^2+x$, which evaluates to $0$ for all values in ${\mathbb{F}}_2$.

How many $f$ of degree exactly $d<p$ are there such that $f(0)=a$ for some fixed $a\in \{0,1,\dots ,p-1\}$? To have a polynomial of degree $d$, it must hold that $c_d>0$. Since all coefficients must be in the set of residuals $\{0,1,\dots ,p-1\}$, then there are $p$ values for the first $d$ coefficients (including the constant), and exactly $p-1$ (excluding the zero) values for the leading coefficient. Therefore, the number of functions of degree $d$ must be $(p-1)p^d$.

Consider $\mathrm{GF}(5)$. How many polynomials of degree at most $4$ are there that fit through $3$ points? Polynomials of degree $\le 4$ can be made using $5$ points maximum. As such, there are $p^2=5^2=25$ possibilities for the other two unspecified coefficients. This includes polynomials of degrees $2$ and $3$.

For a more intuitive explanation, consider the polynomial,
$p(x)=c_4{x}^4+c_3{x}^3+\dots +a.$

Then, if $c_4=0$ and $c_3=0$, $p(x)$ is a degree-2 polynomial. There is one unique degree-2 polynomial that passes through $3$ points.

If $c_3\ne 0$ (and $c_4=0$), then there are $p-1$ options for the leading coefficient for a degree-3 polynomial. This leaves us with $4$ choices.

If $c_4\ne 0$ (and $c_3\in \{0,\dots ,\}$), then there are $p-1$ options for $c_4$ and $p$ options for $c_3$, which is $(p-1)p$ polynomials in total. In this case, $20$.

Therefore, there are exactly $1+4+20=25$ polynomials of degree at most $4$ that fit through $3$ points in $\mathrm{GF}(5)$

(Medium) Lagrange Interpolation in Finite Fields

In this problem, we will break down the terms of Lagrange interpolation by working through an example, where we want to find a unique polynomial $p(x)$ of degree at most $2$ that passes through points $(-1,3)$, $(0,1)$, and $(1,2)$ in ${\mathbb{F}}_5$.

First, assume we have polynomials $p_{-1}(x)$, $p_0(x)$, and $p_1(x)$ satisfying:

p_{-1}(0) &\equiv p_{-1}(1) \equiv 0 \pmod{5}; & p_{-1}(-1) &\equiv 1 \pmod{5} \\ p_{0}(-1) &\equiv p_{0}(1) \equiv 0 \pmod{5}; & p_{0}(0) &\equiv 1 \pmod{5} \\ p_{1}(-1) &\equiv p_{1}(0) \equiv 0 \pmod{5}; & p_{1}(1) &\equiv 1 \pmod{5} \end{align}$$ >[!example]- Construct $p(x)$ using a linear combination of $p_{-1}(x)$, $p_{0}(x)$, and $p_{1}(x)$. >It holds that $p(x)=3p_{-1}(x) + p_{0}(x) + 2p_{1}(x)$. >[!example]- Find $p_{-1}(x)$. In other words, find a degree 2 polynomial that has roots at x = 0 and x = 1 and

evaluates to 1 at x =−1 (all in modulo 5).

Equivalent Polynomials