5
$\begingroup$

Can someone explain me why and how a left multiplication of an element of a finite field GF(2^k) can be seen as a linear transformation on GF(2^k) over GF(2)? I read this https://www.maa.org/sites/default/files/Wardlaw47052.pdf but it is not clear to me.

Thank you!

$\endgroup$
5
$\begingroup$

Let's look at something you are hopefully more familiar with and that is the complex and real numbers. Every complex number can be written uniquely as $a + bi$ with $a, b \in \mathbf R$. This means that $\{1, i\}$ is linearly independent over $\mathbf R$ (it is a basis of $\mathbf C$ over $\mathbf R$). A linear transformation of $\mathbf C$ over $\mathbf R$ is a function $T : \mathbf C \to \mathbf C$ such that

  • $T(w + z) = T(w) + T(z)$ for every $w, z \in \mathbf C$
  • $T(az) = aT(z)$ for every $z \in \mathbf C$ and $a \in \mathbf R$

Every such transformation takes the form

$$ T(a + bi) = (ar + bs) + (at + bu)i, $$

for some real numbers $r,s,t,u$. We can write this equation in matrix form as

$$ \begin{pmatrix} r & s \\ t & u \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} ar + bs \\ at + bu \end{pmatrix}. $$

For instance, the complex conjugation map $T(a + bi) = a - bi$ corresponds to the matrix equation

$$ \begin{pmatrix} 1 & 0 \\ 0 & - 1 \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} a \\ -b \end{pmatrix}. $$

We can also consider the map $T(a + bi) = (c + di)(a + bi)$ (that is, $T$ multiplies on the left by $c + di$). Expanding this out we have

$$T(a + bi) = (c + di)(a + bi) = (ac - bd) + (ad + bc)i, $$

which corresponds to the matrix equation

$$ \begin{pmatrix} c & -d \\ d & c \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} ac - bd \\ ad + bc \end{pmatrix}. $$

For ${\rm GF}(2^k)$ over ${\rm GF}(2)$ it is the same idea but instead of $\{1, i\}$ as a basis you have some other basis.

$\endgroup$
  • $\begingroup$ Thank you. I added an answer at this topic to ask you if I understood well. $\endgroup$ – Bruce Wayne Dec 13 '17 at 11:57
8
$\begingroup$

The field $\operatorname{GF}(2^k)$ is a finite dimensional vector space over $\operatorname{GF}(2)$ for $k$ any integer greater zero, so we can talk about linear transformations on this vector space. Let $\alpha \in \operatorname{GF}(2^k)$ and define the following map

$$ \begin{align} T_\alpha: \operatorname{GF}(2^k) &\to \operatorname{GF}(2^k) \\ x & \mapsto \alpha x \end{align} $$

That is, $T_\alpha$ is a map which takes an element of $x \in \operatorname{GF}(2^k)$ and maps it to $\alpha x \in \operatorname{GF}(2^k)$. This is the multiplication map you are talking about. This is indeed a linear transformation since for $x, y \in \operatorname{GF}(2^k)$ and $c \in \operatorname{GF}(2)$ we have that

$$ T_\alpha(x + y) = \alpha(x + y) = \alpha x + \alpha y = T_\alpha(x) + T_\alpha(y) $$

and

$$ T_\alpha(cx) = \alpha(cx) = c(\alpha x) = cT_\alpha(x) $$


Edit: As mentioned in the comment by lhf, all of the above argument still holds if the field extension $\operatorname{GF}(2^k)/\operatorname{GF}(2)$ is replaced by an arbitrary field extension $L/K$. It is not necessary that the field $K$ be finite, nor is it necessary that the degree of the extension be finite. This is readily seen because the fact that $L$ is a vector space over $K$, as well as linearity of $T_\alpha$ follows simply from the field axioms and the fact that $K$ is a subfield of $L$.

$\endgroup$
  • $\begingroup$ This works for any field extension. $\endgroup$ – lhf Dec 13 '17 at 10:06
  • $\begingroup$ Thank you for your accurate answer! $\endgroup$ – Bruce Wayne Dec 13 '17 at 18:23
1
$\begingroup$

Thank you for your answers. So, let us suppose to have $\mathbb{F}_{2^3}$ over $\mathbb{F}_{2}$, with $\mathbb{F}_{2^3}=\dfrac{\mathbb{F}_{2}[x]}{<x^3+x+1>}$. A basis is $\{1,\alpha,\alpha^{2}\}$, with $\alpha^{3}=\alpha+1$. Let us consider the left multiplication by a generic element $a_{0}+a_{1}\alpha+a_{2}\alpha^{2}$. So, $$(a_{0}+a_{1}\alpha+a_{2}\alpha^{2})(b_{0}+b_{1}\alpha+b_{2}\alpha^{2})$$ and one have $(a_{0}b_{0}+a_{2}b_{1}+a_{1}b_{2})+(a_{0}b_{1}+a_{1}b_{0}+a_{1}b_{2}+a_{2}b_{2})\alpha+(a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0}+a_{2}b_{1}+a_{2}b_{2})\alpha^2$.

The matrix representation is $$\begin{bmatrix} a_{0} & a_{2} & a_{1} \\ a_{1} & a_{0} & a_{1}+a_{2} \\ a_{2} & a_{1}+a_{2} & a_{0}+a_{2} \end{bmatrix} \begin{bmatrix} b_{0} \\ b_{1} \\ b_{2}. \end{bmatrix}$$ So, if we multiply for $\alpha$ we have that $a_{0}=0, a_{1}=1$ and $a_{2}=0$ so that we obtain \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix} which is the companion matrix of $x^3+x+1$. Is that correct?

$\endgroup$
  • $\begingroup$ $$(a_{0}b_{0}+a_{2}b_{1}+a_{1}b_{2})+(\color{purple}{a_{2}b_{1}} + a_{0}b_{1}+a_{1}b_{0}+a_{1}b_{2}+a_{2}b_{2})\alpha+(a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0}+a_{2}b_{2})\alpha^2$$ giving us the matrix $$ \begin{bmatrix} a_{0} & a_{2} & a_{1} \\ a_{1} & a_{0}+a_{2} & a_{1} + a_{2} \\ a_{2} & a_{1} & a_{0}+a_{2} \end{bmatrix} $$ $\endgroup$ – Trevor Gunn Dec 13 '17 at 15:56
  • $\begingroup$ Otherwise what you've done is correct. $\endgroup$ – Trevor Gunn Dec 13 '17 at 16:05
  • $\begingroup$ Oops, sorry for the mistake! Thank you for the explanation. $\endgroup$ – Bruce Wayne Dec 13 '17 at 18:22
  • 1
    $\begingroup$ The field $\frac{\mathbb{F}_{2}[x]}{\langle x^{3}+x+1 \rangle}$ is $\mathbb{F}_{2^3} = \mathbb{F}_{8}$, not $\mathbb{F}_{2^{8}}$. $\endgroup$ – Morgan Rodgers Dec 15 '17 at 2:06

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.