# How calculation over $GF(2^2)$ is executed?

I was unable to understand the calculation procedure given for $GF(2^m)^2$ in the follwing pdf: http://faculty.washington.edu/manisoma/ee540/EE540finite.pdf

In page 21 of the pdf, "Inversion over Composite Field $GF((2^m)^2)$" is introduced using irreducible polynomial "$x^2+x+\phi$". (The "$\phi$" represents a constant binary {10}.)

However, I can not understand some calculation procedures such as "$a_0\ \texttt{&}\ (a_0+a_1)$" and "$\phi\ \texttt{&}\ a_1$".

What is the calculation procedure in concrete digits ?

• & is probably bitwise AND. Dec 6, 2016 at 9:13
• most programming languages indeed define & to be bitwise AND, additionally this notation should be documented somewhere in your course prior to using it here. Dec 6, 2016 at 9:47

Summary: Addition is bit-wise xor. Multiplication (which you denote as $\&$), is polynomial multiplication in the field $\mathbb{F}_{2^m}$, i.e. modulo some irreducible polynomial of degree $m$ over $\mathbb{F}_2$.
We construct $\mathbb{F}_{(2^m)^2}$ in such a way that it contains an element $x$ such that $P(x)=0$. Since this is a polynomial of degree 2, and it splits in $\mathbb{F}_{(2^m)^2}$, there exist also a $y\in\mathbb{F}_{(2^m)^2}$ such that $$X^2+X+\phi=(X-x)(X-y),$$ where $P(X)=X^2+X+\phi$ is a polynomial in $\mathbb{F}_{2^m}[X]$.
It follows that $xy=\phi$ and $x+y=-1$, hence $y=\frac{\phi}{x}$ and $y=-x-1$. Therefore \begin{align} (a_0+a_1x)^{-1} &= (a_0+a_1x)^{-1}(a_0+a_1y)^{-1}(a_0+a_1y) \\ &= (a_0^2+a_0a_1y+a_0a_1x+a_1^2xy)^{-1}(a_0+a_1y) \\ &= (a_0^2-a_0a_1+a_1^2\phi)^{-1}(a_0+a_1y) \\ &= (a_0(a_0-a_1)+a_1^2\phi)^{-1}(a_0-a_1x-a_1) \\ &= (a_0(a_0+a_1)+a_1^2\phi)^{-1}(a_0+a_1+a_1x). \\ \end{align} This is how you arrive at the inverse.
Now note that $a_0,a_1,\phi\in\mathbb{F}_{2^m}$, so all operations to compute $(a_0(a_0+a_1)+a_1^2\phi)$ are in the field $\mathbb{F}_{2^m}$. In other words, addition is just bit-wise xor. Multiplication is polynomial multiplication modulo an irreducible polynomial over $\mathbb{F}_2$ of degree $m$.
Moreover, this means that the inversion $(a_0(a_0+a_1)+a_1^2\phi)^{-1}$ is also computed in the field $\mathbb{F}_{2^m}$, hence we have reduced inversion in $\mathbb{F}_{(2^m)^2}$ to an inversion in $\mathbb{F}_{2^m}$ plus some cheap stuff.