Finite fields

Let us first warn everyone that, for those who have taken abstract algebra courses (groups, rings, fields), this section might be super boring 😊 This is our attempt to teach finite fields to (non-mathematician) computer scientists in an intuitive way without having to formally introduce groups, rings, and fields. OK, let's try!

Let us try to further understand the proofs of Theorem 43 and Theorem 44. Would the proofs work if we work with polynomials with integer coefficients instead of reals? It doesn't seem so (notice that the interpolation requires division of numbers and a division of two integers may not give us an integer). However, a more careful scrutiny should convince you that we only need to be able to add, subtract, multiply and divide numbers. This exactly corresponds to the concept of fields - it is a set that allows us to do all these operations, e.g., reals, complex numbers, and rational numbers are fields, while integers are not.

Recall that the set of integers modulo a prime also allows all these operations (since, due to Lemma 10, every non-zero number has an inverse!) For a prime $p$, denote by ${\mathbb F}_p = GF(p) = \{0,\ldots, p-1\}$ the set of integers modulo $p$. The set of all polynomials with coefficients coming from this set is denoted by ${\mathbb F}_p[x]$.

Example 44

Consider two polynomials in ${\mathbb F}_2[x]$. We have $f(x) = x^2 +x$ and $g(x) = x^4+x^2 + 1$. Their sum is $(f+g)(x) = x^4 + 2 x^2 + x+1 = x^4+ x +1 \pmod{2}$.

Example 45

Consider $f(x) = (x^2 + 2x+1) \in {\mathbb F}_3[x]$. This polynomial has one root since $f(0) = 1, f(1) = 1$ and $f(2) = 0$, so $2$ is the only root.

Working with polynomials in a finite field may be somewhat counter-intuitive at first, e.g., $x^2+2x+1$ is the same as $x^2 - x -2$ in ${\mathbb F}_3[x]$. Sometimes using negative coefficients is convenient when working with interpolation.

Example 46

What is the unique degree-2 polynomial in ${\mathbb F}_3$ that has $f(0)=f(1) =1$ and $f(2) = 2$? We can calculate $L_0, L_1, L_2$ as follows:

$L_0(x) = \frac{(x-1)(x-2)}{(0-1)(0-2)} = \frac{(x-1)(x-2)}{2} = 2(x-1)(x-2)$

(the last step follows from $2^{-1} \equiv 2 \pmod{3}$). Using similar calculation, we can get

$L_1(x)= 2x(x-2),\ L_2(x)= 2x(x-1)$

After that we can get

$f(x) = \sum_{i} y_i L_i(x) = 2x^2+x +1$

Please try to understand how this works before reading forward.

Exercise 122

Consider degree-$d$ polynomials in ${\mathbb F}_p[x]$ where $p \geq d+1$ is a prime. In this exercise you will prove that, for all $k \in \{0,1,\ldots, d+1\}$ and for all $k$ points $(x_1,y_1),\ldots, (x_k,y_k)\in {\mathbb F}_p^2$ (with distinct $x_i$'s), there are $p^{d-k+1}$ polynomials $f$ that agree with all these points (i.e., $f(x_i)= y_i$ for all $i \in [k]$.)

• Why is the claim true for $k= d+1$? Just say the name of a theorem and a few words.

• Consider the case when $k = d$. Describe a bijection between ${\mathbb F}_p$ and the set of degree-$d$ polynomials in ${\mathbb F}_p[x]$ that agree with the input points. Argue explicitly that it is a bijection (so it will imply the claim for $k=d$).

• Argue why the proof in the previous part can be extended for any value of $k < d$.