2
$\begingroup$

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 ?

$\endgroup$
  • 2
    $\begingroup$ & is probably bitwise AND. $\endgroup$ – fkraiem Dec 6 '16 at 9:13
  • 1
    $\begingroup$ most programming languages indeed define & to be bitwise AND, additionally this notation should be documented somewhere in your course prior to using it here. $\endgroup$ – SEJPM Dec 6 '16 at 9:47
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.