Structure constants for $\mathbb{F}_q$ as an $\mathbb{F}_p$-algebra

Question

Let $k'=\mathbb{F}_q$ and $k=\mathbb{F}_p$, where $q=p^d$. We may regard $k'$ as a $d$-dimensional $k$-algebra via $k\hookrightarrow k'$. For any choice of $k$-basis $\{e_1,\ldots,e_d\}$ we obtain structure constants $a_{ij}^l$ giving the multiplication of basis elements:

$$e_i\cdot e_j=\sum_{l=1}^da_{ij}^le_l$$

I'm trying to define this algebra structure on $\mathbb{F}_q$ in Magma, so I need an explicit description of the $a_{ij}^l$. Is there a way to pick a particularly nice basis so that we can arrive at a formula for the $a_{ij}^l$?

I tried starting with $e_1$, a generator of the multiplicative units of $k'$, and considering the basis of the images of $e_1$ under the Galois group, that is, $e_i=e_1^{p^i}$. But it is not clear to me how to express $e_1^{p^i+p^j}$ as a linear combination of the $e_l$.

Answer 1

Eltseq, when applied to, e.g., an element of GF(q) will give you the coefficients of an element of $\mathbb{F}_q$ relative to the power basis. I'm not sure if you have to construct the field in a special way to get this to work.

Are you sure whatever you're trying to do can't be done with magma's finite field functionality instead?

Answer 2

An extensive survey of vector space representations of finite extensions $\mathbb{F}_q$ over $\mathbb{F}_p$ is Topics in Normal Bases of Finite Fields by N. A. Carella (2001).

Since additions and subtractions are highly efficient operations with respect to most bases, the main focus is on multiplication and multiplicative inverse algorithms with respect to the various bases of the finite fields $\mathbb{F}_{q^n}$ over $\mathbb{F}_q$.

As Commented before, we can construct $\mathbb{F}_q$ as a quotient ring $\mathbb{F}_p[x]/(f(x))$ for any (monic) irreducible polynomial $f(x) \in \mathbb{F}_p[x]$ of degree $d$. As a rough approximation $1/d$ of the monic polynomials of degree $d$ will turn out to be irreducible, so with a good test for irreduciblity in hand, random trials can be a satisfactory way to find some suitable $f(x)$.

An obvious basis is then $\{1,x,\ldots,x^{d-1}\}$, and the ease with which a table of products $x^j x^k = x^{j+k}$ can be expressed in this basis depends on the special structure of $f(x)$. Often, but not always, we may find an irreducible polynomial of the required degree of the form $f(x) = x^d + ax + b$. For characteristic $p=2$ there are few coefficients $a,b$ to use, so generally we can only hope for another trinomial or even a pentanomial to be irreducible. Note in particular that if $d$ is a multiple of eight, there are no irreducible trinomials of degree $d$ over $\mathbb{F}_2$. The odd characteristic $p$ cases lacking irreducible binomial or trinomial polynomials are explored by Hanson, Panario, and Thomson.

If a trinomial $f(x)$ is available, then the multiplication table for its power basis $\{1,x,\ldots,x^{d-1}\}$ will have monomial entries $x^{j+k}$ when $j+k \lt d$ and binomial entries for the rest.

The extension $\mathbb{F}_q$ over $\mathbb{F}_p$, $q=p^d$ for prime $p$, is the splitting field for $x^{p^d}-x$ and hence always a Galois extension. By normal basis is meant a basis which is the orbit of some element $\eta \in \mathbb{F}_q$ under the action of the Galois group of $\mathbb{F}_q$ over $\mathbb{F}_p$. A normal basis would be especially useful for an application requiring frequent $p$th powers or roots. See Carella's survey linked above for more details and applications.