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.
Answer
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.
No comments:
Post a Comment