1
$\begingroup$

I've been reading this article XOR-counts and lightweight multiplication with fixed elements in binary finite fields and I came across the term Multiplication matrix and I've wondered if that's some terminology from finite fields theory I perhaps don't know (English is not my native language and I don't study math in English). It seems really odd that the author mentions the term in an abstract and doesn't define it properly (but then maybe it's just a widely used term).
From what I've understood multiplication matrix is matrix such that: $\forall \alpha \in \mathbb{F}_{2^n} \exists A \in \mathbb{F}_2$ such that $\forall x \in \mathbb{F}_{2^n}: \alpha \cdot x = A \cdot \hat{x}$, where $\hat{x}$ is element $x$ written as an n-dimensional vector over $\mathbb{F}_2$. Thank you for any help.

$\endgroup$
1
$\begingroup$

Multiplication by an element of $\mathbb F_{2^n}$ on elements of $\mathbb F_{2^n}$ produces a $\mathbb F_2$ linear transformation on $\mathbb F_{2^n}$. As such, you can pick a basis of $\mathbb F_{2^n}$ (necessarily having $n$ elements) and find a transformation matrix (an element of $M_n(\mathbb F_2)$) for each element.

Then the explanation in the paper is quite clear (p 286, the second page of the pdf):

Our goal in this work is to explore some connections and properties of the direct and sequential XOR-count metrics and then to apply these to get some theoretical results regarding optimal implementations of matrices that represent multiplication with a fixed field element $α ∈ \mathbb F_{2^k}$. Optimal choices of these matrices (called multiplication matrices) can then be used for local optimizations of matrices over $\mathbb F_{2^k}$.

As mentioned in the paper in several places, they are optimizing to minimize the number of XOR operations required to perform multiplication.

$\endgroup$
  • $\begingroup$ Could you please describe a way to finding such a transformation matrix? I realize that when I pick a basis $B$, the element $\alpha x$ has only one way of being written in this basis. I just can't think of a way to get matrix $A$ from $x$ and $\alpha x$. I can even think of a general example where multiple matrices that fulfill these criteria exist. Does $B^{-1}AB$ change with basis? By my geometrical intuition, it shouldn't, since linear transformation just a rotation of vector space. But I guess that might be the goal of this article: to find in which basis has $[A]_B$ the lowest XOR-count. $\endgroup$ – kytka Sep 24 at 21:49
  • $\begingroup$ @kytka it is too complicated to write in a comment, and it sounds anyway like you need to struggle through the details yourself. It is a simple thing, except if you have not really understood how a matrix represents a transformation in terms of a particular basis. I would advise you to construct the field of four elements, then choose a basis over the field of two elements, then pick an element that is not 0 or 1, and work out what its matrix is. $\endgroup$ – rschwieb Sep 25 at 2:34

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.