Computations in finite fields
1. Addition and multiplication
For clarity, let us consider the $8$-element finite field which is defined by the irreducible polynomial $\alpha^3+\alpha+ 1$. Then any computation is just arithmetic with polynomials with the exception that the end result must be reduced modulo $\alpha^3+\alpha+ 1$. For instance, \[\begin{align*} (\alpha^2+ \alpha+ 1)(\alpha^2+ 1) % &= \alpha^4+ \alpha^3+ \alpha^2 + \alpha^2+ \alpha+ 1\\ &= \alpha^4+ \alpha^3+ \alpha+ 1 =\alpha^2+\alpha\enspace. \end{align*}\]
Create a function in IPython for adding two elements of a field $\mathbb Z_{2^k}$, with $k$ and the coefficients of the two polynomials to be added given as input.
Create a function in IPython for multiplying two elements of a field $\mathbb Z_{2^k}$, with $k$, the coefficients of the polynomial defining the field and the coefficients of the two polynomials to be multiplied given as input. (Note that the second half of the multiplication algorithm — reducing the degree of the product to be less than $k$ — is what was described in lesson Long division of polynomials and actually this second half of this exercise was one exercise in that lesson.)
2. Computing inverses
2.1 Extended Euclid's algorithm
The easiest way to invert an element is to use extended Euclid's algorithm. Let $a(\alpha)$ and $b(\alpha)$ be two polynomials. Then for the extended Euclid's algorithm we must divide elements in the following manner: \[\begin{align*} a(\alpha) &= q_1(\alpha) b(\alpha) + r_1(\alpha)\\ b(\alpha) &= q_2(\alpha) r_1(\alpha) + r_2(\alpha)\\ r_1(\alpha) &= q_3(\alpha) r_2(\alpha) + r_3(\alpha)\\ &\cdots\\ r_n(\alpha) & = q_{n+2}(\alpha) r_{n+1}(\alpha)+r_{n+2}(\alpha)\\ r_{n+1}(\alpha)&=q_{n+3}(\alpha)r_{n+2}(\alpha) \end{align*}\] and then express $r_{n+2}(\alpha)$ as $r_{n+2}(\alpha)= r_n(\alpha)- q_{n+2}(\alpha) r_{n+1}(\alpha)$. In most cases, terms $r_n(\alpha)$ and $r_{n+1}(\alpha)$ are not $a(\alpha)$ and $b(\alpha)$. Hence, we must express them from the previous equations. As a result, we start to substitute one by one equations: \[\begin{align*} r_{n+1}(\alpha) &=r_{n-1}(\alpha)- q_{n+1}(\alpha) r_{n}(\alpha)\\ &\cdots\\ r_3(\alpha) &= r_1(\alpha)- q_3(\alpha) r_2(\alpha) \\ r_2(\alpha) &= b(\alpha) - q_2(\alpha) r_1(\alpha) \\ r_1(\alpha)&= a(\alpha) - q_1(\alpha) b(\alpha)\enspace. \end{align*}\] Although this process is very error prone to carry out with pen and pencil, it leads to a final expression \[\begin{align*} r_{n+1}=u(\alpha)a(\alpha)+v(\alpha)b(\alpha)\enspace. \end{align*}\]
2.2 Computing inverses
To invert a field element $a(\alpha)$ modulo $p(\alpha)$ you have to carry out the extended Euclid's algorithm for $a(\alpha)$ and $b(\alpha)=p(\alpha)$. The inverse is $u(\alpha)$.
For example, let us consider the specific finite field $\mathbb{F}_{2^8}=\mathbb{Z}_2[\alpha]/(\alpha^8+\alpha^4+\alpha^3+\alpha+1)$, which is used in the Advanced Encryption Standard. Let us find inverses of $\alpha$ and $\alpha^7+\alpha^3+\alpha$. To this end, we must find polynomials $u_1(\alpha), v_1(\alpha), u_2(\alpha), v_2(\alpha)$ over $\mathbb{Z}_2$ such that \[\begin{align*} \alpha\cdot u_1(\alpha)+ (\alpha^8+\alpha^4+\alpha^3+\alpha+ 1) \cdot v_1(\alpha)=1\\ (\alpha^7+\alpha^3+\alpha)\cdot u_2(\alpha)+ (\alpha^8+\alpha^4+\alpha^3+\alpha+ 1)\cdot v_2(\alpha)=1 \end{align*}\] Let us use the Euclidean algorithm for that.
Since \[\begin{align*} \alpha^8+\alpha^4+\alpha^3+\alpha+ 1 = \alpha(\alpha^7+\alpha^3+\alpha^2+1) + 1 \end{align*}\] over $\mathbb{Z}_2$, we can express \[\begin{align*} \alpha\cdot (\alpha^7+\alpha^3+\alpha^2+1) + (\alpha^8+\alpha^4+\alpha^3+\alpha+1)\cdot 1 = 1\enspace. \end{align*}\] The polynomial $u_1(\alpha)=\alpha^7+\alpha^3+\alpha^2+ 1$ is the inverse of $\alpha$, as \[\begin{align*} \alpha\cdot (\alpha^7+\alpha^3+\alpha^2+ 1) = \alpha^8+\alpha^4+\alpha^3+\alpha = 1 \enspace. \end{align*}\]
To find the second inverse, note that \[\begin{align*} \alpha^8+\alpha^4+\alpha^3+\alpha+1 % &= \alpha\cdot(\alpha^7+\alpha^3+\alpha) + \alpha^3 + \alpha^2 + \alpha + 1\\ \alpha^7+\alpha^3+\alpha & =(\alpha^4+\alpha^3)\cdot(\alpha^3 + \alpha^2 + \alpha + 1) + \alpha\\ \alpha^3+ \alpha^2+\alpha+ 1 &=(\alpha^2+\alpha+1)\cdot \alpha + 1 \end{align*}\] and thus \[\begin{align*} 1 &= 1\cdot(\alpha^3+ \alpha^2+\alpha+1)+(\alpha^2+\alpha+1)\cdot \alpha\\ \alpha % &=1\cdot(\alpha^7+\alpha^3+\alpha) +(\alpha^4+\alpha^3)\cdot(\alpha^3 + \alpha^2 + \alpha + 1)\\ \alpha^3+\alpha^2+\alpha+1 &= 1\cdot(\alpha^8+\alpha^4+\alpha^3+\alpha+1) + \alpha\cdot(\alpha^7+\alpha^3+\alpha) \end{align*}\] Systematic substitution of terms allows us to represent $1$ as a linear combination of terms $\alpha^8+\alpha^4+\alpha^3+\alpha+1$ and $\alpha^7+\alpha^3+\alpha$: \[\begin{align*} 1 % &=1\cdot(\alpha^3+ \alpha^2+\alpha+1)+(\alpha^2+\alpha+1)\cdot ((\alpha^7+\alpha^3+\alpha) +(\alpha^4+\alpha^3)\cdot(\alpha^3 + \alpha^2 + \alpha + 1))\\ &= (\alpha^2+\alpha+1)\cdot(\alpha^7+\alpha^3+\alpha) + (\alpha^6+\alpha^3+1)(\alpha^3+\alpha^2+\alpha+1)\\ &= (\alpha^2+\alpha+1)\cdot(\alpha^7+\alpha^3+\alpha) + (\alpha^6+\alpha^3+1)\cdot((\alpha^8+\alpha^4+\alpha^3+\alpha+1) + \alpha(\alpha^7+\alpha^3+\alpha))\\ &= (\alpha^6+\alpha^3+1)\cdot(\alpha^8+\alpha^4+\alpha^3+\alpha+1) + (\alpha^7+\alpha^4+\alpha^2+1)\cdot (\alpha^7+\alpha^3+\alpha) \end{align*}\] and thus $(\alpha^7+\alpha^3+\alpha)^{-1}= \alpha^7+\alpha^4+\alpha^2+1$.
Create a function in IPython for computing the inverse of an element in a field $\mathbb Z_{2^k}$ (with $k$, the coefficients of the polynomial defining the field and the coefficients of the polynomial to be inverted given as arguments).
Consider a finite field $\mathbb{F}_{32}$ specified by the polynomial $\alpha^5+\alpha^3+ 1$. Using IPython, find the inverses of all elements that contain $\alpha^4$ in their representation.