====== - #5 Computations in finite fields ====== ===== - 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 [[02_long_division_of_polynomials]] and actually this second half of this exercise was one exercise in that lesson.) ===== - Computing inverses ===== ==== - 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*}\] ==== - 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. ++++ Answer | ^ element $x$ ^ its inverse $x^{-1}$ ^ | $\alpha^4$ | $\alpha^4 + \alpha^2 + \alpha$ | | $\alpha^4 + 1$ | $\alpha^4 + \alpha$ | | $\alpha^4 + \alpha$ | $\alpha^4 + 1$ | | $\alpha^4 + \alpha + 1$ | $\alpha^4 + \alpha^2 + \alpha + 1$ | | $\alpha^4 + \alpha^2$ | $\alpha$ | | $\alpha^4 + \alpha^2 + 1$ | $\alpha^4 + \alpha^3 + 1$ | | $\alpha^4 + \alpha^2 + \alpha$ | $\alpha^4$ | | $\alpha^4 + \alpha^2 + \alpha + 1$ | $\alpha^4 + \alpha + 1$ | | $\alpha^4 + \alpha^3$ | $\alpha + 1$ | | $\alpha^4 + \alpha^3 + 1$ | $\alpha^4 + \alpha^2 + 1$ | | $\alpha^4 + \alpha^3 + \alpha$ | $\alpha^3 + \alpha^2 + \alpha$ | | $\alpha^4 + \alpha^3 + \alpha + 1$ | $\alpha^4 + \alpha^3 + \alpha^2 + \alpha$ | | $\alpha^4 + \alpha^3 + \alpha^2$ | $\alpha^3 + \alpha^2 + 1$ | | $\alpha^4 + \alpha^3 + \alpha^2 + 1$ | $\alpha^2 + \alpha + 1$ | | $\alpha^4 + \alpha^3 + \alpha^2 + \alpha$ | $\alpha^4 + \alpha^3 + \alpha + 1$ | | $\alpha^4 + \alpha^3 + \alpha^2 + \alpha + 1$ | $\alpha^3 + \alpha^2 + \alpha + 1$ | ++++ [[06_groups]]