In many cryptographic applications, polynomials in only one variable are not enough and we need to deal with polynomials in two or more variables. In this section, we define such polynomials and we see how to sum and multiply them.

We begin with two variables, \(x\) and \(y\).
A term or monomial in the two variables \(x\) and \(y\) is a product of powers, i.e.
\(x^{i}y^{h}\), for some \(i,h\) in \(\mathbb{N}\).
For example, we can consider the following monomials

Be careful that for example \(x^{-4}\) and \(xy^{-1}\) are not monomials.
With monomials, we can define polynomials in the two variables \(x\) and \(y\) and coefficients in \(\mathbb{F}_{2}\) (i.e. multivariate polynomials in the field of bits) as sums of monomials (without coefficients). For example, the following are polynomials

(a monomial is also a polynomial).
Formally, a polynomial in the two variables \(x\) and \(y\) and coefficients in \(\mathbb{F}_{2}\) is any expression of the form

such that

• •

  for each \(i,h\) in \(\mathbb{N}\), \(a_{i,h}\in\mathbb{F}_{2}\),

• •

  only a finite number of coefficients is nonzero.

The set containing all polynomials in \(x,y\) with bits as coefficient is denoted by \(\mathbb{F}_{2}[x,y]\).

The \(x\)-degree of a term \(x^{i}y^{h}\) in the two variables \(x,y\) is the value \(i\), whereas \(h\) is its \(y\)-degree. To be more precise

The total degree (or, simply, degree) of a term \(x^{i}y^{h}\) in the two variables \(x,y\) is the sum of its \(x\)-degree and its \(y\)-degree, i.e.

If we consider \(xy^{5}\), then \(\deg_{x}(xy^{5})=1\), \(\deg_{y}(xy^{5})=5\), and \(\deg(xy^{5})=6\).
The degree of a polynomial \(f\in\mathbb{F}_{2}[x,y]\) is the highest degree of the monomials appearing in \(f\) with nonzero coefficient, so, if \(f=x^{3}y+xy^{6}-y^{2}\), then \(\deg(f)=\deg(xy^{6})=7\), and if \(g=x^{3}+y\) then \(\deg(g)=\deg(x^{3})=3\).

Two polynomials \(f,g\in\mathbb{F}_{2}[x,y]\) are called equal if

a term \({x}^{i}y^{j}\) appears in \(f\) with nonzero coefficient \(a_{i,j}\) if and only if \({x}^{i}y^{j}\) appears in \(g\) with coefficient \(a_{i,j}\).

Then, we can see that, in \(\mathbb{F}_{2}[x,y]\), \(x^{3}+0y^{12}=x^{3}=x^{3}+0xy^{32}\).
Similarly to what presented in section \ref{Sec:Polynomials} for univariate polynomials, the sum and the product of polynomials in \(\mathbb{F}_{2}[x,y]\) are defined analogously to real polynomials, but of course we must take into account that their coefficients are bits. The following examples will clarify this point.

Since we can multiply polynomials in \(x,y\), we can raise them at a power \(m\), with the usual meaning: \(f\mapsto f^{m}\).
If, for example, we take the polynomial \(f=x^{3}+y+1\in\mathbb{F}_{2}[x,y]\), we have that

As in the univariate case, raising a multivariate polynomial in \(\mathbb{F}_{2}[x,y]\) to the power 2 is the same as raising its monomials to the power 2 and summing them.
 

We consider now the case of three variables, \(x\), \(y\) and \(z\).
A term or monomial in the three variables \(x\), \(y\) and \(z\) is a product of powers, i.e. \(x^{i}y^{h}z^{l}\), for some \(i,h,l\) in \(\mathbb{N}\).
For example, we can consider the following monomials

With monomials, we can define polynomials in the variables \(x\), \(y\) and \(z\) and coefficients in \(\mathbb{F}_{2}\) as sums of monomials (without coefficients). For example, the following are polynomials

(a monomial is also a polynomial).
Formally, a polynomial in the three variables \(x\), \(y\) and \(z\) and coefficients in \(\mathbb{F}_{2}\) is any expression of the form

such that

• •

  for each \(i,h,l\) in \(\mathbb{N}\), \(a_{i,h,l}\in\mathbb{F}_{2}\),

• •

  only a finite number of coefficients is nonzero.

The set containing all polynomials in \(x,y,z\) with bits as coefficient is denoted by \(\mathbb{F}_{2}[x,y,z]\).

The \(x\)-degree of a term \(x^{i}y^{h}z^{l}\) in the three variables \(x,y,z\) is the value \(i\), whereas \(h\) is its \(y\)-degree and \(l\) its \(z\)-degree. To be more precise

The total degree (or, simply, degree) of a term \(x^{i}y^{h}z^{l}\) in the three variables \(x,y,z\) is the sum of its \(x\)-degree, its \(y\)-degree and its \(z\)-degree, i.e.

If we consider \(xy^{5}z^{3}\) then \(\deg_{x}(xy^{5}z^{3})=1\), \(\deg_{y}(xy^{5}z^{3})=5\), \(\deg_{z}(xy^{5}z^{3})=3\), and \(\deg(xy^{5}z^{3})=9\).
The degree of a polynomial \(f\in\mathbb{F}_{2}[x,y,z]\) is the highest degree of the monomials appearing in \(f\) with nonzero coefficient, so, if \(f=x^{3}z+xy^{8}-z^{2}y\), then \(\deg(f)=\deg(xy^{8})=9\), and if \(g=xz^{3}+xyz\) then \(\deg(g)=4\).

Two polynomials \(f,g\in\mathbb{F}_{2}[x,y,z]\) are called equal if

a term \({x_{1}}^{i}y^{h}z^{l}\) appears in \(f\) with nonzero coefficient \(a_{i,h,l}\) if and only if \({x_{1}}^{i}y^{h}z^{l}\) appears in \(g\) with coefficient \(a_{i,h,l}\).

Then, \(x^{3}+0y^{12}=x^{3}=x^{3}+0xyz^{32}\) and \(xyz=0x^{3}+xyz+0y^{4}+0z\).

The sum and the product of polynomials in \(\mathbb{F}_{2}[x,y,z]\) follow the usual rules.

Since we can multiply polynomials in \(x,y,z\), we can raise them at any power.
If, for example, we take the polynomial \(f=x^{3}z+y+z+1\in\mathbb{F}_{2}[x,y,z]\), we have that

As in the univariate case, raising a multivariate polynomial in \(\mathbb{F}_{2}[x,y,z]\) to the power 2 is the same as raising to the power 2 its monomials and summing them.

Now we are ready to tackle the generic case of \(n\) variables: \({x_{1}},{x_{2}},...,x_{n}\)
A term or monomial in the \(n\) variables \({x_{1}},...,x_{n}\) is a product of powers of \({x_{1}},...,x_{n}\), i.e. \({x_{1}}^{i_{1}}\cdots x_{n}^{i_{n}}\) for some \(i_{1},...,i_{n}\in\mathbb{N}\).
For example, for three variables \({x_{1}},{x_{2}},{x_{3}}\), it is clear that \({x_{1}}^{3}{x_{2}}^{8}{x_{3}}^{6}\), \({x_{2}}{x_{3}}^{4}={x_{1}}^{0}{x_{2}}{x_{3}}^{4}\) ,\({x_{1}}^{4}={x_{1}}^{4}{x_{2}}^{0}{x_{3}}^{0}\) are all terms.
With terms, we can define polynomials in \(n\) variables \({x_{1}},...,x_{n}\) and coefficients in \(\mathbb{F}_{2}\) (i.e. multivariate polynomials in the field of bits) as expressions of the form

such that

• •

  for each \(i_{1},...,i_{n}\in\mathbb{N}\), \(a_{i_{1},...,i_{n}}\in\mathbb{F}_{2}\),

• •

  only a finite number of coefficients is nonzero.

The set containing all polynomials in \(n\) variables \({x_{1}},...,x_{n}\) with coefficients in \(\mathbb{F}_{2}\) is denoted by \(\mathbb{F}_{2}[{x_{1}},...,x_{n}]\).
Note that

• •

  \({x_{2}}^{2}{x_{3}}+{x_{1}}\) is a polynomial in \(\mathbb{F}_{2}[{x_{1}},{x_{2}},{x_{3}}]\); but it is not a polynomial in \(\mathbb{F}_{2}[{x_{1}},{x_{2}}]\);

• •

  \({x_{1}}-\frac{1}{2}{x_{2}}\) is not a polynomial in \(\mathbb{F}_{2}[{x_{1}},{x_{2}}]\);

• •

  \({x_{1}}{x_{2}}{{x_{3}}}^{3}+1\) is a polynomial in \(\mathbb{F}_{2}[{x_{1}},{x_{2}},{x_{3}}]\).

When (as we have done before) we will deal with two or three variables, we may denote them as \(x,y\) or \(x,y,z\).
For \(1\leq j\leq n\), the \(x_{j}\)-degree of a term in \(n\) variables \({x_{1}}^{i_{1}}\cdots x_{n}^{i_{n}}\) is the value \(i_{j}\). To simplify the expression we can use \(\deg_{j}=\deg_{x_{j}}\) i.e.

The total degree (or, simply, degree) of a term \(t\) in \(n\) variables \(t={x_{1}}^{i_{1}}\cdots x_{n}^{i_{n}}\) is the sum of all \(\deg_{j}(t)^{\prime}\)s for all \(1\leq j\leq n\), i.e.

If we consider \({x_{1}}{x_{3}}^{5}{x_{4}}^{2}\), then \(\deg_{1}({x_{1}}{x_{3}}^{5}{x_{4}}^{2})=1\), \(\deg_{2}({x_{1}}{x_{3}}^{5}{x_{4}}^{2})=0\), \(\deg_{3}({x_{1}}{x_{3}}^{5}{x_{4}}^{2})=5\), \(\deg_{4}({x_{1}}{x_{3}}^{5}{x_{4}}^{2})=2\) and \(\deg({x_{1}}{x_{3}}^{5}{x_{4}}^{2})=8\).
The degree of a polynomial \(f\in\mathbb{F}_{2}[{x_{1}},...,x_{n}]\) is the highest degree of the monomials appearing in \(f\) with nonzero coefficient, so, if \(f={x_{1}}^{3}{x_{2}}+{x_{1}}{x_{2}}^{6}-{x_{3}}^{10}{x_{2}}\), then \(\deg(f)=\deg({x_{3}}^{10}{x_{2}})=11\).

Two polynomials \(f,g\in\mathbb{F}_{2}[{x_{1}},...,x_{n}]\) are called equal if

a term \({x_{1}}^{i_{1}}\cdots x_{n}^{i_{n}}\) appears in \(f\) with nonzero coefficient \(a_{i_{1}...i_{n}}\) if and only if \({x_{1}}^{i_{1}}\cdots x_{n}^{i_{n}}\) appears in \(g\) with coefficient \(a_{i_{1}...i_{n}}\) as well.

Note that \(x^{3}+0y^{12}=x^{3}=x^{3}+0xy^{32}\) and \({x_{5}}{x_{4}}-{x_{2}}={x_{5}}{x_{4}}+0{x_{3}}-{x_{2}}\).
The sum, the product and the powers of polynomials in \(\mathbb{F}_{2}[{x_{1}},...x_{n}]\) follow the usual rules.
If, for example, we take the polynomial \(f={x_{3}}{x_{1}}+{x_{4}}+1\), we have that