In many cryptographic applications, as for example in Linear Feedback Shift Registers (LFSRs for short), cryptographers have to deal with polynomials whose coefficients are bits.
In this section we will introduce these polynomials.
Let us start with terms.
A term in the variable \(x\) is a power of \(x\), i.e. \(x^{a}\) for some non-negative integer \(a\in\mathbb{N}\).
For example, \(x^{2}\) or \(x^{100}\), but also \(x=x^{1}\) and \(1=x^{0}\).
With terms we can define polynomials, since a polynomial in the variable \(x\) and
coefficients in \(\mathbb{F}_{2}\) (i.e. a polynomial
over the field of bits)
is any expression of the form \(a_{0}+a_{1}x+a_{2}x^{2}+...+a_{n}x^{n}\), where \(a_{0},...,a_{n}\in\mathbb{F}_{2}\) are
bits and \(x^{i},i=0,...n\) are terms.
For example, \(x+x^{5}\) and \(x^{3}+x^{10}+x^{21}\) are polynomials over \(\mathbb{F}_{2}\), while \(\frac{1}{2}x+\frac{2}{11}x^{10}-x^{11}\)
is not.
The set \(\mathbb{F}_{2}[x]\) contains all polynomials in the variable \(x\) whose coefficients are bits:
\begin{equation} \mathbb{F}_{2}[x]\,=\,\{1,x,x+1,x^{2},x^{2}+x,....\}\,.\nonumber \\ \end{equation}The notation is the analogue of that for real polynomials, whose set is
usually denoted by \(\mathbb{R}[x]\).
In analogy with \(\mathbb{R}[x]\), we can define the degree of a monomial
\(x^{\alpha}\in\mathbb{F}_{2}[x]\) as the positive integer \(\alpha\). For
example, the degree of \(x^{5}\) is \(5\) and the degree of \(1\) is \(0\).
The degree of a polynomial \(f\) is the maximal degree of the monomials appearing
in \(f\) with nonzero coefficient. Since the monomials in \(\mathbb{F}_{2}[x]\) are only power
of \(x\), the degree of \(f\) is actually the maximal power of \(x\) appearing in \(f\).
The degree of the polynomial \(f=0\) is conventionally set to \(-\infty\).
As an example, the degree of \(0\cdot x^{7}+1\cdot x^{5}+x^{4}+x^{2}+x\) is \(5\), since the coefficient of \(x^{7}\)
is zero and the coefficient of \(x^{5}\) is \(1\).
Two polynomials are called equal if they have the same degree \(d\) and, for each \(i=0,...,d\), term
\(x^{i}\) has the same coefficient in both.
For example \(x^{2}+x+1\,=\,0x^{4}+x^{2}+x+1\).
Having understood polynomials, we pass to perform operations with them.
First, we explain how to sum two polynomials.
This operation is defined exactly as that with real polynomials, but one has to take into account that the coefficients are bits,
so they have to be summed with the “\(+\)” operation we defined for bits.
For example, if \(x^{3}+x^{2}\) and \(x^{2}+x+1\) are in \(\mathbb{F}_{2}[x]\), then
Since \(1+1=0\) in \(\mathbb{F}_{2}\), we finally get
\begin{equation} (x^{3}+x^{2})+(x^{2}+x+1)\;=\;x^{3}+x+1\,.\nonumber \\ \end{equation}Compute the following sums:
\((x^{3}+x^{2}+x+1)+(x^{4}+x^{2}+x)\)
\((x^{10}+x^{7}+x+1)+(x^{5}+x)+(x^{7}+1)\)
\(x+(x^{8}+x^{5}+1)+(x^{6}+x^{2}+x)\)
As with the sum, the product of two polynomials is defined as the usual product of real polynomials, but taking into account that their coefficients are bits. For example
\begin{equation} (x^{3}+x^{2})\cdot(x^{2}+x)\;=\;x^{5}+x^{4}+x^{4}+x^{3}\;=\;x^{5}+(1+1)x^{4}+x^{3}\;=\;x^{5}+x^{3}\,.\nonumber \\ \end{equation}We observe that \(\mathbb{F}_{2}[x]\) is a group with the sum, as you can check by yourself. You can even show that \(\mathbb{F}_{2}[x]\) is very close to being a field, since multiplication and addition distribute and multiplication would give rise to a group, except that, for example, there is no multiplicative inverse of \(x\) in \(\mathbb{F}_{2}[x]\). So the only missing property for \(\mathbb{F}_{2}[x]\) is the existence of multiplicative inverse for any nonzero element, which is exactly the same situation for \(\mathbb{Z}\).
Find the degree of the following polynomials
\((x^{4}+x^{3}+1)\cdot(x^{3}+x^{2}+1)\)
\((x^{3}+x^{2}+x)+(x^{4}+x^{3})\)
\((x^{2}+x+1)+(x^{2}+x)\)
Give your comments on the degree of \(f\cdot g\) and \(f+g\), with \(f,g\in\mathbb{F}_{2}[x]\).
Since we can multiply polynomials, we can also raise them to powers, with the usual meaning
\begin{equation} f^{n}=\underbrace{f\cdots f}_{n}\nonumber \\ \end{equation}Consider for example the polynomial \(f(x)=x+1\in\mathbb{F}_{2}[x]\) and suppose to compute its square power \((x+1)^{2}\). This means multiplying \(f\) by itself so
\begin{equation} f(x)^{2}=f(x)\cdot f(x)=(x+1)\cdot(x+1)=x^{2}+x+x+1=x^{2}+(1+1)x+1=x^{2}+1.\nonumber \\ \end{equation}We notice that \(x^{2}+1=x^{2}+(1)^{2}\), so we can write \((x+1)^{2}=x^{2}+(1)^{2}\).
Check by examples that in general raising a polynomial in \(\mathbb{F}_{2}\) to the power \(2\) is the same as raising to the power \(2\) its monomials and summing them.
The property shown in exercise \ref{RaisingTo2} is not shared by the analogous operation for real polynomials. Indeed, if we consider \(q(x)=x+1\in\mathbb{R}[x]\), we have - as it is well-known since school - \(q(x)^{2}=(x+1)^{2}=x^{2}+2x+1\), which is different from \(x^{2}+1\).
When we learn at school how to raise the binomial \(x+1\) to a power \(\alpha\), we learn the construction of
the so-called Pascal’s (or Tartaglia’s) Triangle. We can repeat the same construction on \(\mathbb{F}_{2}[x]\):
\((x+1)^{0}=1\rightarrow\mathbf{1}\)
\((x+1)^{1}=x+1\rightarrow\mathbf{1\;1}\)
\((x+1)^{2}=x^{2}+1\rightarrow\mathbf{1\;0\;1}\)
\((x+1)^{3}=x^{3}+x^{2}+x+1\rightarrow\mathbf{1\;1\;1\;1}\)
\((x+1)^{4}=x^{4}+1\rightarrow\mathbf{1\;0\;0\;0\;1}\)
and so on.
We have then constructed the Triangle:
Compute the following powers over \(\mathbb{F}_{2}[x]\)
\((x^{2}+x)^{2}\)
\((x^{3}+x+1)^{2}\)
\((x+1)^{4}\)
\((x^{2}+x+1)^{3}\)
Give your comments about powers of polynomials with even exponents.
Provide a link between the Pascal’s Triangle in \(\mathbb{Z}[x]\) and the new version of the triangle defined here.
Each polynomial \(f\in\mathbb{F}_{2}[x]\) can be seen as a function \(f:\mathbb{F}_{2}\rightarrow\mathbb{F}_{2}\), such that
\begin{equation} 0\mapsto f(0)\qquad 1\mapsto f(1)\nonumber \\ \end{equation}where \(f(i),i\in\mathbb{F}_{2}\) is the bit we get by substituting \(x\) with \(i\) in \(f\) and simplifying the obtained expression.
If \(f_{1}=x^{3}+x+1\) we get
\begin{equation} f_{1}(0)=0^{3}+0+1=0+0+1=1\nonumber \\ \end{equation}and
\begin{equation} f_{1}(1)=1^{3}+1+1=1+1+1=1.\nonumber \\ \end{equation}On the other hand, if we consider \(f_{2}=x^{3}+x\) then
\begin{equation} f_{2}(0)=0^{3}+0=0\nonumber \\ \end{equation}and
\begin{equation} f_{2}(1)=1^{3}+1=0.\nonumber \\ \end{equation}Finally, if we take \(f_{3}=x^{4}+1\),
\begin{equation} f_{3}(0)=0^{4}+1=1\nonumber \\ \end{equation}and
\begin{equation} f_{3}(0)=1^{4}+1=0.\nonumber \\ \end{equation}As shown by the above example, the evaluation of a polynomial \(p\) in \(i\in\mathbb{F}_{2}\)
can return \(0\) or \(1\). If it returns \(0\) we say that \(i\) is a root of
\(p\).
With the notation of example \ref{Eval}, neither \(0\) nor \(1\) are roots of \(f_{1}\), while
both \(1\) and \(0\) are roots of \(f_{2}\) and only \(1\) is a root of \(f_{3}\).
Compute the roots in \(\mathbb{F}_{2}\) of the following polynomials in \(\mathbb{F}_{2}[x]\):
\(x^{4}+x^{3}+x\)
\(x^{3}+x+1\)
\(x^{6}+x^{5}+1\)
\(x^{4}+x^{3}+x^{2}+x\).
How many functions \(\mathbb{F}_{2}\rightarrow\mathbb{F}_{2}\) exist?
To answer this question, we will follow the following steps:
as we already know, given a polynomial \(p(x)\in\mathbb{F}_{2}[x]\), we can evaluate it at the elements of \(\mathbb{F}_{2}\), i.e. we can compute \(p(0)\) and \(p(1)\), which clearly belong to \(\mathbb{F}_{2}\), by mere substitution. Can you find two different polynomials \(f,g\in\mathbb{F}_{2}[x]\) s.t. they have the same evaluations, i.e. \(f(0)=g(0)\) and \(f(1)=g(1)\)?
Let us think now about the possible values we can have via evaluation.
Given \(f\in\mathbb{F}_{2}[x]\), we evaluate it at \(0\) and so \(f(0)\) can be either \(0\) or \(1\) and, in the same way, \(f(1)\) can be either \(0\) or \(1\).
We summarize in the following table the values a polynomial can assume if evaluated in \(\mathbb{F}_{2}\):
| a | p(a) | q(a) | r(a) | s(a) |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
As an example, if\(p=x^{2}+x\), then \(p(0)=0\) and \(p(1)=0\) as in column \(2\) of the table; if
\(q=x^{2}+x+1\), then \(q(0)=q(1)=1\) as in the third column. If \(r=x^{3}\), we have \(r(0)=0\) and \(r(1)=1\) as in column four. Finally, if \(s=x^{2}+1\) we have \(s(0)=1\) and \(s(1)=0\), as in the last column of the table.
Can you find other polynomials \(p^{\prime},q^{\prime},r^{\prime},s^{\prime}\in\mathbb{F}_{2}[x]\) of minimal degree such that, evaluated in \(0,1\) behave exactly as \(p,q,r\) and \(s\)?
Looking at Table \ref{FourFunctions}, guess how many functions \(\mathbb{F}_{2}\rightarrow\mathbb{F}_{2}\) exist.
There is a property for polynomials that plays a special role in cryptography. We introduce it formally in the following definition and then we discuss it.
A nonzero polynomial \(f\in\mathbb{F}_{2}[x]\) of degree \(\geq 1\) is called reducible if there exist \(q,r\in\mathbb{F}_{2}[x]\) of positive degree such that their product is \(f\), i.e.
\begin{equation} f\,=\,q\,r\,.\nonumber \\ \end{equation}If no polynomials of this form exist, then \(f\) is an irreducible polynomial.
Polynomials of degree \(1\) are clearly irreducible.
Consider the polynomial \(f=x^{4}+x^{2}+x\in\mathbb{F}_{2}[x]\). Clearly
\(f=x(x^{3}+x+1)\) and so \(f\) is reducible.
We also note that \(f(0)=0\), so \(0\) is a root of \(f\).
A famous theorem due to Ruffini ensures that a polynomial \(p\in\mathbb{F}_{2}[x]\) has a root
\(a\in\mathbb{F}_{2}\) if and only if it can be written as \(p=(x+a)q\) for a certain \(q\in\mathbb{F}_{2}[x]\). A special case is when \(f=(x+a)\), in this case \(q=1\). In all other cases, \(p\) is then irreducible.
For low-degree polynomials we can strenthen Ruffini’s theorem in the following theorem.
A polynomial \(p\in\mathbb{F}_{2}[x]\) of degree \(2\) or \(3\) is reducible if and only
if it has at least a root in \(\mathbb{F}_{2}\).
Or, equivalently,
A polynomial \(p\in\mathbb{F}_{2}[x]\) of degree \(2\) or \(3\) is irreducible if and only
if it has no roots in \(\mathbb{F}_{2}\).
Consider the polynomial \(p(x)=x^{3}+x+1\). Its degree is \(3\) and we have
\(p(0)=p(1)=1\) so \(p\) has no roots in \(\mathbb{F}_{2}\). By Theorem \ref{ThIrred} it is
irreducible.
On the other hand \(q(x)=x^{2}+1\) has degree \(2\) and it holds \(p(0)=1,\,p(1)=0\),
so \(1\) is a root of \(q(x)\). Indeed \(q(x)\) is reducible and it can be decomposed
as \(q(x)=(x+1)(x+1)=(x+1)^{2}.\)
Factorize the following polynomials in \(\mathbb{F}_{2}[x]\):
\(p_{1}=x^{5}+x^{4}+x+1\)
\(p_{2}=x^{4}+x^{2}+1\)
Hint: try all possible irreducible factors of degree \(1\) and \(2\).
Find all the irreducible polynomials of degree \(2\) in \(\mathbb{F}_{2}[x]\).
Use this result to prove that \(f=x^{4}+x+1\) is irreducible in \(\mathbb{F}_{2}[x]\).
In order to complete our study on polynomial operations, we have
to define one more operation: the division of polynomials.
A consequence of more advanced theory for polynomials with coefficients in a field is the
following. If we consider two polynomials \(f\) and \(g\) in \(\mathbb{F}_{2}[x]\),
we can find two other polynomials, say \(q,r\), such that \(f=g\cdot q+r\) and \(\deg(r)<\deg(g)\).
The polynomial \(q\) is called quotient, whereas \(r\) is the
remainder. If \(r=0\) then we say that \(g\) divides \(f\), or that
we have performed an exact division between \(f\) and \(g\).
Let us consider \(f=x^{2}+1,\,g=x\) in \(\mathbb{F}_{2}[x]\); we clearly have \(q=x\) and \(r=1\):
\begin{equation} x^{2}+1=x\cdot x+1.\nonumber \\ \end{equation}If we consider \(f=1+x^{2},\,g=x+1\) in \(\mathbb{F}_{2}[x]\), we note that \(x^{2}+1=(x+1)\cdot(x+1)\), so \(q=g\) and \(r=0.\)
Let us consider \(f=x,\,g=x^{2}+1\) in \(\mathbb{F}_{2}[x]\); this case is special since we cannot perform any division and we obviously have \(q=0\) and \(r=f\).
Let us now see how to compute the quotient and the reminder; we will use
\(f=x^{2}+1,\,g=x\) in \(\mathbb{F}_{2}[x]\) as a simple example.
We start reordering the monomials in \(f\) and the monomials in \(g\) in
decreasing order by degree.
Then we put the polynomials in a table, as follows
| \(x^{2}\) | \(+0x\) | \(+1\) | \(x\) |
If in \(f(x)\) a term of degree smaller than \(\deg(f)\) does not appear, we put
it in the table with coefficient zero.
Now we divide the term of maximal degree of \(f\) by that of \(g\),
getting a new monomial \(m\); in our particular case \(m=x\)
| \(x^{2}\) | \(+0x\) | \(+1\) | \(x\) |
| \(x\) |
Then, we multiply \(m\cdot g\) and we insert the result in the table under \(f\), so that the terms of same degree are lined-up.
| \(x^{2}\) | \(+0x\) | \(+1\) | \(x\) |
| \(x^{2}\) | \(+0x\) | \(+0\) | \(x\) |
We sum the lined-up monomials (remember that the coefficients belong to \(\mathbb{F}_{2}\), so \(1+1=0\)!!!!); the obtained sum is the partial reminder of our division.
| \(x^{2}\) | \(+0x\) | \(+1\) | \(x\) |
|---|---|---|---|
| \(x^{2}\) | \(+0x\) | \(+0\) | \(x\) |
| \(0x^{2}\) | \(+0x\) | \(+1\) | \(x\) |
If the partial remainder’s degree is greater than or equal to the degree of \(g\), then repeat the procedure; otherwise, stop and observe that
the polynomial under \(g\) is the quotient \(q\)
the partial remainder is the (final) remainder \(r\)
In our example \(q=x\) and \(r=1\).
Perform the division between the following polynomials in \(\mathbb{F}_{2}[x]\)
\(f=x^{5}+1\), \(g=x^{3}+x+1\)
\(f=x^{3}+x^{2}+1\), \(g=x^{3}+1\);
\(f=x^{4}+x\), \(g=x+1\);
\(f=x^{5}+x^{3}+1\), \(g=x^{2}+x+1\);
\(f=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1\), \(g=x^{3}+x^{2}+1\).
Which of them are exact divisions?