The polynomials in \(\mathbb{F}_{2}[x]\) are infinite. However, if we bound the degree, we find a finite set, as for example
\begin{equation} S:=\{p\in\mathbb{F}_{2}[x]|\deg(p)<3\}=\{0,1,x,x+1,x^{2},x^{2}+x,x^{2}+1,x^{2}+x+1\}.\nonumber \\ \end{equation}This set contains \(8\) polynomials; indeed, \(f\in S\) if and only if \(f\) is of the form
\begin{equation} f=a_{0}+a_{1}x+a_{2}x^{2},\,a_{0},a_{1},a_{2}\in\mathbb{F}_{2}\nonumber \\ \end{equation}Since there are two choices for each coefficient \(a_{0},a_{1},a_{2}\) the polynomials are \(2^{3}=8\). If we take two polynomials \(f,g\) in \(S\), then also \(f+g\) belongs to \(S\), since when we sum two polynomials, the degree cannot grow (see Exercise \ref{degree}), according to the rule in \(\mathbb{F}_{2}[x]\)
\begin{equation} \deg(f+g)\leq\deg(f),\deg(g);\qquad\deg(f+g)<\deg(f),\deg(g)\iff\deg(f)=\deg(g).\nonumber \\ \end{equation}However, if we multiply \(f,g\), their product \(fg\) can be outside \(S\); for example
\begin{equation} f=x^{2}+1,\,g=x+1\quad\implies\quad(x^{2}+1)(x+1)=x^{3}+x^{2}+x+1\,.\nonumber \\ \end{equation}We describe a way to make \(S\) ”closed with respect to multiplication”,that is, we want to define a special operation on the polynomials in \(S\) that allows their product to remain in \(S\). We do that by what is called a ”polynomial relation”. For example, we can define the following relation \(x^{3}=x+1\), or equivalently \(x^{3}+x+1=0\). With this relation in mind, any time we find a monomial of degree greater than or equal to \(3\) we substitute \(x^{3}\) with \(x+1\). We iterate this substitution until we obtain a polynomial of degree strictly less than \(3\). For example
\begin{equation} x^{5}+x\,=\,x^{2}(\underline{x^{3}})+x\,=^{\mathrm{substitution}}\,x^{2}(\underline{x+1})+x\,=\,\underline{x^{3}}+x^{2}+x=^{\mathrm{substitution}}\underline{x+1}+x^{2}+x\,=\,x^{2}+1\,.\nonumber \\ \end{equation}The crucial observation here is that we can obtain the same result by dividing the polynomial \(x^{5}+x\) by the polynomial \(g=x^{3}+x+1\): the remainder is \(x\) (see Exercise \ref{QuoRemEx}).
Indeed, we can consider a set \(T\), which collects the remainders of the divisions of all polynomials in \(F_{2}[x]\) by \(g\). It is easy to see that \(T\) contains \(S\), because when
we divide a polynomial \(f\) of degree less than \(3\) by \(g\), the remainder is \(f\) itself
(see Example \ref{QuotRemStrange}), so
On the other hand, if we consider any polynomial \(f\notin S\), this has \(\deg(f)\geq 3\) and when we divide it by \(g\), we will get a remainder of degree strictly less than \(\deg(g)=3\), and so \(T\) can only contain polynomials of degree at most \(2\), therefore
\begin{equation} T=S=\{0,1,x,x+1,x^{2},x^{2}+x,x^{2}+1,x^{2}+x+1\}\,.\nonumber \\ \end{equation}We can perform this construction in general. Let \(g\) be in \(F_{2}[x]\), with \(\deg(g)=n\). We consider the set \(A\) of polynomials that collects all remainders of the division by \(g\)
\begin{equation} A\,=\,\{\textrm{remainders by }g\}\,.\nonumber \\ \end{equation}This set is finite, because the degree of its polynomials is at most \(n-1\), and again it actually contains all polynomials with degree at most \(n-1\)
\begin{equation} A\,=\,\{0,1,x,x+1,\ldots,x^{n-1},x^{n-1}+1,\ldots,x^{n-1}+x^{n-2}+\cdots+x+1\}\,.\nonumber \\ \end{equation}Also in this general setting, we can sum and multiply. The sum is obvious, the multiplication may require some divisions by \(g\) before we can arrive at a small-degree polynomial.
Let us consider the polynomial \(g=x^{2}+x+1\in\mathbb{F}_{2}[x]\) and define the set \(A_{1}\,=\,\{\textrm{remainders by }g\}\,.\) For this particular \(g\), we have \(A_{1}=\{0,1,x,x+1\}\). We want to show that \(A_{1}\) is a field. We recall the definition of field, namely that \(A_{1}\) should satisfy the following properties
\(A_{1}\) is an abelian group w.r.t. the sum of polynomials;
\(A_{1}\setminus\{0\}=\{1,x,x+1\}\) is an abelian group w.r.t. the product of polynomials;
\((f+g)\cdot h=fh+gh\), for any \(f,g,h\in A_{1}\).
Since \(A_{1}\) is formed by polynomials, properties i) and iii) are obvious. As regards ii), we need only to prove that each nonzero element in \(A_{1}\) has an inverse:
\(1\cdot 1=1\) so \(1\) is the inverse of itself;
\(x(x+1)=\underline{x^{2}}+x=^{\mathrm{substitution}}\,\underline{(x+1)}+x=x+1+x=1\), so in \(A_{1}\),
\begin{equation} \frac{1}{x+1}=x,\,\qquad\frac{1}{x}=x+1.\nonumber \\ \end{equation}The polynomial \(g=x^{2}+x+1\) of the above example is irreducible (prove it using Theorem \ref{ThIrred}); in the next example, we see what happens if the polynomial we consider is reducible.
Consider the polynomial \(h=x^{2}+1\). We can easily note that it is reducible, since \(h=(x+1)^{2}\). Let us call \(A_{2}\) the set of remainders modulo \(h\). We see that \(A_{2}=\{0,1,x,x+1\}\), which is apparently the same \(A_{1}\) of the previous example. However we must distinguish \(A_{1}\) from \(A_{2}\), because the relation imposed on \(A_{2}\) by \(h\) does not make it a field. We prove it by showing that \(x+1\in A_{2}\setminus\{0\}\) has no inverse. Indeed
\((x+1)\cdot 1=x+1\neq 1\);
\((x+1)\cdot x=\underline{x^{2}}+x=^{\mathrm{substitution}}\,\underline{1}+x\neq 1\);
\((x+1)(x+1)=\underline{x^{2}}+1=^{\mathrm{substitution}}\,\underline{1}+1=0\neq 1\).
For cryptographic reasons we are especially interested in the case of \(g_{256}=x^{8}+x^{4}+x^{3}+x^{2}+1\in\mathbb{F}_{2}[x]\). We define \(\mathbb{F}_{256}:=\{p\in\mathbb{F}_{2}[x]\mid\deg(p)<8\}\). As explained above \(\mathbb{F}_{256}\) is the set of the remainders of divisions by \(g_{256}\), i.e.
\begin{equation} \mathbb{F}_{256}=\{0,1,,x,x+1,\ldots,x^{8},\ldots,x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\}\,.\nonumber \\ \end{equation}The following fundamental theorem explains the different behaviour of the polynomials sets in the two previous examples:
Let \(g\) be in \(\mathbb{F}_{2}[x]\). We consider the set \(A\) of polynomials that collects all remainders of the division by \(g\)
\begin{equation} A\,=\,\{\textrm{remainders by }g\}\,.\nonumber \\ \end{equation}Then \(A\) is a field if and only if \(p\) is an irreducible polynomial.
List all irreducible polynomials of degree \(2\) and \(3\), proving irreducibility by showing that the remainders’ set is a field.
Thanks to Theorem \ref{IrrField} and the fact that \(g_{256}\) is irreducible, the following corollary holds
\(\mathbb{F}_{256}\) is a field.
The field \(\mathbb{F}_{256}\) is so important that it deserves a name: the byte field. Its elements are called bytes. You may have met bytes already in computer science courses and they looked different from polynomials, so in the next subsection we will show you the connection between the representation of bytes in polynomial form (which is that used in cryptography) and more common representations (hex values and bit strings).