In the next section, where we will construct finite fields other than $\mathbb Z_n$, we will need to calculate the remainder when one polynomial is divided with another. It might come as a surprise that you can do such thing with polynomials — but actually this is very much like the division of integers.
Recall that the quotient and remainder of integers were defined as follows: if $a$ is an integer and $b$ a positive integer, then there exists a unique pair of integers $(q, r)$ such that $a = qb + r$ and $0 \leq r < b$; the number $q$ is called the quotient and $r$ the remainder of the division of $a$ by $b$. The definition of division of polynomials is analogous.
Let $a$ and $b$ be polynomials with coefficients in some field (e. g. real numbers $\mathbb R$ or in the finite field $\mathbb Z_p$ where $p$ is a prime number) such that $b$ is not the zero polynomial. Then there exists unique pair of polynomials $(q, r)$ with coefficients in the same field such that $a = qb + r$ and the degree of $r$ is strictly less than the degree of $b$. The polynomial $q$ is called the quotient and $r$ the remainder of the division of $a$ by $b$.
For example, let's compute the quotient and remainder of dividing the polynomial $a(X) = 4X^3 + 5X^2 + X + 5$ by $b(X) = 2X^2+X+2$. As $b$ is a quadratic polynomial, i. e. a polynomial of degree $2$, we expect the remainder to be a polynomial of degree $1$ or $0$, i. e. a linear or constant polynomial.
To compute the quotient and remainder of polynomials, recall first the integer long division algorithm taught in elementary school (maybe your schoolbooks used a slightly different format, but the idea is surely familiar): \[ \begin{array}[t]{l} 300\ :\ 7 = 42,\text{ remainder }6\\ \dfrac{28\hphantom{2}}{\hphantom{2}20}\\ \hphantom{3} \dfrac{14}{\hphantom{1}6}\\ \end{array} \] So we found that $300 = 42 \cdot 7 + 6$.
Division of polynomials uses exactly the same algorithm. \[ \begin{array}[t]{l} \,\,(4X^3 + 5X^2 \hphantom{.5}+ \hphantom{4}X + 5)\ :\ (2X^2+X+2) = 2X + 1.5,\ \text{remainder }-4.5X+2\\ \hphantom{(}\dfrac{4X^3 + 2X^2 \hphantom{.5}+4X \hphantom{{}+5}}{\hphantom{4X^3+{}} 3X^2 \hphantom{.5}- 3X + 5}\\ \hphantom{(}\hphantom{4X^3+{}} \dfrac{3X^2+1.5X+3}{\hphantom{3X^2}-4.5X+2}\\ \end{array} \] So we found that $4X^3 + 5X^2 + X + 5 = (2X + 1.5)(2X^2+X+2) + (-4.5X+2)$. You can check the result by opening the braces.
Compute the quotient and remainder of the division of polynomial $a(X) = 6X^5 - 4X^4 - 6X^3 + X^2 +1$ by $b(X) = 3X^2 - 2X - 1$ over the field $\mathbb R$. Answer
In the example above, we computed within the set of real numbers $\mathbb R$. In cryptography it is actually even more common to consider polynomials with over the residue class field $\mathbb Z_2$, i. e. with coefficients in $\mathbb Z_2$. This is even easier since every coefficient is either $0$ and $1$. If after a subtraction we get a coefficient $-1$ after a subtraction, we may replace it with $1$ since $-1 = 1$ in $\mathbb Z_2$. E. g.
\[ \begin{array}[t]{l} \,\,(X^3 \hphantom{{} + X^2 + X} + 1)\ :\ (X^2+X+1) = X + 1,\text{ remainder }0\\ \hphantom{(}\dfrac{X^3 + X^2 + X \hphantom{{}+1}}{\hphantom{X^3+{}} X^2 + X + 1}\\ \hphantom{(}\hphantom{X^3+{}}\dfrac{X^2+X+1}{\hphantom{X^2+X+{}}0}\\ \end{array} \]
So we found that $X^3+1 = (X+1)(X^2+X+1)$ in $\mathbb Z_2$. We can check if we haven't made a mistake by opening the braces: $(X+1)(X^2+X+1) = (X^3+X^2+X) + (X^2+X+1) = X^3 + 2X^2 + 2X + 1 = X^3+1$ indeed.
In school you have probably learned the formula $X^3+Y^3=(X+Y)(X^2-XY+Y^2)$, which as a special case gives $X^3+1 = (X+1)(X^2-X+1)$. That formula actually holds in any field; it agrees with our result since in the field $\mathbb Z_2$, we have $-1 = 1$ and thus $X^2-X+1=X^2+X+1$.
Compute the quotient and remainder of the division of polynomial $a(X) = X^5 + X^4 + X + 1$ by $b(X) = X^3 + 1$ over the field $\mathbb Z_2$. Answer
Write a function in IPython for computing the quotient and remainder of the long division of two polynomials over the field $\mathbb Z_2$. (Of course, test it too, that it gives correct results — e. g. with the polynomials of the previous exercise or the example above.)
In fields $\mathbb Z_n$ where $n > 2$ the algorithm is slightly more complicated than in $\mathbb Z_2$ because there exist coefficients greater than 1, but is analogous to the long division in $\mathbb R$. We leave it to the reader to figure out the difference from the polynomial long division algorithm in $\mathbb R$ (using exactly the same computations as in $\mathbb R$ is not good, since the quotient and remainder might get fractional coefficients, as we saw in the example above, but we want quotient and remainder with coefficients in $\mathbb Z_n$). However, in cryptography (and in following the lessons of this topic) one mainly deals with polynomials with coefficients in $\mathbb Z_2$.
Compute the quotient and remainder of the division of polynomial $a(X) = 6X^5 + 3X^4 + X^3 + X^2 +1$ by $b(X) = 3X^2 + 5X + 6$ over $\mathbb Z_7$. Answer