# Normal basis

In mathematics, specifically the algebraic theory of fields, a normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of fields has a normal basis. In algebraic number theory, the study of the more refined question of the existence of a normal integral basis is part of Galois module theory.

## Normal basis theorem

Let $F\subset K$ be a Galois extension with Galois group $G$. The classical normal basis theorem states that there is an element $\beta \in K$ such that $\{g(\beta ):g\in G\}$ forms a basis of K, considered as a vector space over F. That is, any element $\alpha \in K$ can be written uniquely as α=∑$_{g∈G}$a$_g$g(β){\textstyle \alpha =\sum _{g\in G}a_{g}\, g(\beta )} for some elements $a_{g}\in F.$
A normal basis contrasts with a primitive element basis of the form $\{1,\beta ,\beta ^{2},\ldots ,\beta ^{n-1}\}$, where $\beta \in K$ is an element whose minimal polynomial has degree $n=[K:F]$.

## Group representation point of view

A field extension K / F with Galois group G can be naturally viewed as a representation of the group G over the field F in which each automorphism is represented by itself. Representations of G over the field F can be viewed as left modules for the group algebra F[G]. Every homomorphism of left F[G]-modules $\phi :F[G]\rightarrow K$ is of form $\phi (r)=r\beta$ for some $\beta \in K$. Since $\{1\cdot \sigma |\sigma \in G\}$ is a linear basis of F[G] over F, it follows easily that $\phi$ is bijective iff $\beta$ generates a normal basis of K over F. The normal basis theorem therefore amounts to the statement saying that if K / F is finite Galois extension, then $K\cong F[G]$ as a left $F[G]$-module. In terms of representations of G over F, this means that K is isomorphic to the regular representation.

## Case of finite fields

For finite fields this can be stated as follows: Let $F=\mathrm {GF} (q)=\mathbb {F} _{q}$ denote the field of q elements, where q = p$^m$ is a prime power, and let $K=\mathrm {GF} (q^{n})=\mathbb {F} _{q^{n}}$ denote its extension field of degree n ≥ 1. Here the Galois group is $G={\text{Gal}}(K/F)=\{1,\Phi ,\Phi ^{2},\ldots ,\Phi ^{n-1}\}$ with $\Phi ^{n}=1,$ a cyclic group generated by the q-power Frobenius automorphism $\Phi (\alpha )=\alpha ^{q},$with $\Phi ^{n}=1=\mathrm {Id} _{K}.$ Then there exists an element β ∈ K such that $\{\beta ,\Phi (\beta ),\Phi ^{2}(\beta ),\ldots ,\Phi ^{n-1}(\beta )\}\ =\ \{\beta ,\beta ^{q},\beta ^{q^{2}},\ldots ,\beta ^{q^{n-1}}\!\}$ is a basis of K over F.

### Proof for finite fields

In case the Galois group is cyclic as above, generated by $\Phi$ with $\Phi ^{n}=1,$ the normal basis theorem follows from two basic facts. The first is the linear independence of characters: a multiplicative character is a mapping χ from a group H to a field K satisfying $\chi (h_{1}h_{2})=\chi (h_{1})\chi (h_{2})$; then any distinct characters $\chi _{1},\chi _{2},\ldots$ are linearly independent in the K-vector space of mappings. We apply this to the Galois group automorphisms $\chi _{i}=\Phi ^{i}:K\to K,$ thought of as mappings from the multiplicative group $H=K^{\times }$. Now $K\cong F^{n}$as an F-vector space, so we may consider $\Phi :F^{n}\to F^{n}$ as an element of the matrix algebra M$_n$(F); since its powers $1,\Phi ,\ldots ,\Phi ^{n-1}$ are linearly independent (over K and a fortiori over F), its minimal polynomial must have degree at least n, i.e. it must be $X^{n}-1$.
The second basic fact is the classification of finitely generated modules over a PID such as $F[X]$. Every such module M can be represented as M≅⨁$_{i=1}$$^k$ F[X]/(f$_i$(X)) {\textstyle M\cong \bigoplus _{i=1}^{k}{\frac {F[X]}{(f_{i}(X))}}}, where $f_{i}(X)$ may be chosen so that they are monic polynomials or zero and $f_{i+1}(X)$ is a multiple of $f_{i}(X)$. $f_{k}(X)$ is the monic polynomial of smallest degree annihilating the module, or zero if no such non-zero polynomial exists. In the first case dim$_F$⁡M=∑$_{i=1}$$^k$deg⁡f$_i${\textstyle \dim _{F}M=\sum _{i=1}^{k}\deg f_{i}}, in the second case $\dim _{F}M=\infty$. In our case of cyclic G of size n generated by $\Phi$ we have an F-algebra isomorphism F[G]≅ F[X]/(X$^n$−1) {\textstyle F[G]\cong {\frac {F[X]}{(X^{n}-1)}}} where X corresponds to $1\cdot \Phi$, so every $F[G]$-module may be viewed as an $F[X]$-module with multiplication by X being multiplication by $1\cdot \Phi$. In case of K this means $X\alpha =\Phi (\alpha )$, so the monic polynomial of smallest degree annihilating K is the minimal polynomial of $\Phi$. Since K is a finite dimensional F-space, the representation above is possible with $f_{k}(X)=X^{n}-1$. Since $\dim _{F}(K)=n,$ we can only have $k=1$, and K≅ F[X]/(X$^n$−1) {\textstyle K\cong {\frac {F[X]}{(X^{n}{-}\, 1)}}} as F[X]-modules. (Note this is an isomorphism of F-linear spaces, but not of rings or F-algebras.) This gives isomorphism of $F[G]$-modules $K\cong F[G]$ that we talked about above, and under it the basis $\{1,X,X^{2},\ldots ,X^{n-1}\}$ on the right side corresponds to a normal basis $\{\beta ,\Phi (\beta ),\Phi ^{2}(\beta ),\ldots ,\Phi ^{n-1}(\beta )\}$ of K on the left.
Note that this proof would also apply in the case of a cyclic Kummer extension.

### Example

Consider the field $K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}$ over $F=\mathrm {GF} (2)=\mathbb {F} _{2}$, with Frobenius automorphism $\Phi (\alpha )=\alpha ^{2}$. The proof above clarifies the choice of normal bases in terms of the structure of K as a representation of G (or F[G]-module). The irreducible factorization $X^{n}-1\ =\ X^{3}-1\ =\ (X{-}1)(X^{2}{+}X{+}1)\ \in \ F[X]$ means we have a direct sum of F[G]-modules (by the Chinese remainder theorem):$K\ \cong \ {\frac {F[X]}{(X^{3}{-}\,1)}}\ \cong \ {\frac {F[X]}{(X{+}1)}}\oplus {\frac {F[X]}{(X^{2}{+}X{+}1)}}.$ The first component is just $F\subset K$, while the second is isomorphic as an F[G]-module to $\mathbb {F} _{2^{2}}\cong \mathbb {F} _{2}[X]/(X^{2}{+}X{+}1)$ under the action $\Phi \cdot X^{i}=X^{i+1}.$ (Thus $K\cong \mathbb {F} _{2}\oplus \mathbb {F} _{4}$ as F[G]-modules, but not as F-algebras.)
The elements $\beta \in K$ which can be used for a normal basis are precisely those outside either of the submodules, so that $(\Phi {+}1)(\beta )\neq 0$ and $(\Phi ^{2}{+}\Phi {+}1)(\beta )\neq 0$. In terms of the G-orbits of K, which correspond to the irreducible factors of: $t^{2^{3}}-t\ =\ t(t{+}1)\left(t^{3}+t+1\right)\left(t^{3}+t^{2}+1\right)\ \in \ F[t],$ the elements of $F=\mathbb {F} _{2}$ are the roots of $t(t{+}1)$, the nonzero elements of the submodule $\mathbb {F} _{4}$ are the roots of $t^{3}+t+1$, while the normal basis, which in this case is unique, is given by the roots of the remaining factor $t^{3}{+}t^{2}{+}1$.
By contrast, for the extension field $L=\mathrm {GF} (2^{4})=\mathbb {F} _{16}$ in which n = 4 is divisible by p = 2, we have the F[G]-module isomorphism $L\ \cong \ \mathbb {F} _{2}[X]/(X^{4}{-}1)\ =\ \mathbb {F} _{2}[X]/(X{+}1)^{4}.$ Here the operator $\Phi \cong X$ is not diagonalizable, the module L has nested submodules given by generalized eigenspaces of $\Phi$, and the normal basis elements β are those outside the largest proper generalized eigenspace, the elements with $(\Phi {+}1)^{3}(\beta )\neq 0$.

### Application to cryptography

The normal basis is frequently used in cryptographic applications based on the discrete logarithm problem, such as elliptic curve cryptography, since arithmetic using a normal basis is typically more computationally efficient than using other bases.
For example, in the field $K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}$ above, we may represent elements as bit-strings: $\alpha \ =\ (a_{2},a_{1},a_{0})\ =\ a_{2}\Phi ^{2}(\beta )+a_{1}\Phi (\beta )+a_{0}\beta \ =\ a_{2}\beta ^{4}+a_{1}\beta ^{2}+a_{0}\beta ,$ where the coefficients are bits $a_{i}\in \mathrm {GF} (2)=\{0,1\}.$ Now we can square elements by doing a left circular shift, $\alpha ^{2}=\Phi (a_{2},a_{1},a_{0})=(a_{1},a_{0},a_{2})$, since squaring β$^4$ gives β$^8$ = β. This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring.

## Proof for the case of infinite fields

Suppose $K/F$ is a finite Galois extension of the infinite field F. Let [K : F] = n, ${\text{Gal}}(K/F)=G=\{\sigma _{1}...\sigma _{n}\}$, where $\sigma _{1}={\text{Id}}$. By the primitive element theorem there exists $\alpha \in K$ such $i\neq j\implies \sigma _{i}(\alpha )\neq \sigma _{j}(\alpha )$ and $K=F[\alpha ]$. Let us write $\alpha _{i}=\sigma _{i}(\alpha )$. $\alpha$'s (monic) minimal polynomial f over K is the irreducible degree n polynomial given by the formula ${\begin{aligned}f(X)&=\prod _{i=1}^{n}(X-\alpha _{i})\end{aligned}}$ Since f is separable (it has simple roots) we may define ${\begin{aligned}g(X)&=\ {\frac {f(X)}{(X-\alpha )f'(\alpha )}}\\g_{i}(X)&=\ {\frac {f(X)}{(X-\alpha _{i})f'(\alpha _{i})}}=\ \sigma _{i}(g(X)).\end{aligned}}$ In other words, ${\begin{aligned}g_{i}(X)&=\prod _{\begin{array}{c}1\leq j\leq n\\j\neq i\end{array}}{\frac {X-\alpha _{j}}{\alpha _{i}-\alpha _{j}}}\\g(X)&=g_{1}(X).\end{aligned}}$ Note that $g(\alpha )=1$ and $g_{i}(\alpha )=0$ for $i\neq 1$. Next, define an $n\times n$ matrix A of polynomials over K and a polynomial D by ${\begin{aligned}A_{ij}(X)&=\sigma _{i}(\sigma _{j}(g(X))=\sigma _{i}(g_{j}(X))\\D(X)&=\det A(X).\end{aligned}}$ Observe that $A_{ij}(X)=g_{k}(X)$, where k is determined by $\sigma _{k}=\sigma _{i}\cdot \sigma _{j}$; in particular $k=1$ iff $\sigma _{i}=\sigma _{j}^{-1}$. It follows that $A(\alpha )$ is the permutation matrix corresponding to the permutation of G which sends each $\sigma _{i}$ to $\sigma _{i}^{-1}$. (We denote by $A(\alpha )$ the matrix obtained by evaluating $A(X)$ at $x=\alpha$.) Therefore, $D(\alpha )=\det A(\alpha )=\pm 1$. We see that D is a non-zero polynomial, and therefore it has only a finite number of roots. Since we assumed F is infinite, we can find $a\in F$ such that $D(a)\neq 0$. Define ${\begin{aligned}\beta &=g(a)\\\beta _{i}&=g_{i}(a)=\sigma _{i}(\beta ).\end{aligned}}$ We claim that $\{\beta _{1},\ldots ,\beta _{n}\}$ is a normal basis. We only have to show that $\beta _{1},\ldots ,\beta _{n}$ are linearly independent over F, so suppose ∑$_{j=1}$$^n$x$_j$β$_j$=0{\textstyle \sum _{j=1}^{n}x_{j}\beta _{j}=0} for some $x_{1}...x_{n}\in F$. Applying the automorphism $\sigma _{i}$ yields ∑$_{j=1}$$^n$x$_j$σ$_i$(g$_j$(a))=0{\textstyle \sum _{j=1}^{n}x_{j}\sigma _{i}(g_{j}(a))=0} for all i. In other words, $A(a)\cdot {\overline {x}}={\overline {0}}$. Since $\det A(a)=D(a)\neq 0$, we conclude that ${\overline {x}}={\overline {0}}$, which completes the proof.
It is tempting to take $a=\alpha$ because $D(\alpha )\neq 0$. But this is impermissible because we used the fact that $a\in F$ to conclude that for any F-automorphism $\sigma$ and polynomial $h(X)$ over $K$ the value of the polynomial $\sigma (h(X))$ at a equals $\sigma (h(a))$.

## Primitive normal basis

A primitive normal basis of an extension of finite fields E / F is a normal basis for E / F that is generated by a primitive element of E, that is a generator of the multiplicative group K$^×$. (Note that this is a more restrictive definition of primitive element than that mentioned above after the general normal basis theorem: one requires powers of the element to produce every non-zero element of K, not merely a basis.) Lenstra and Schoof (1987) proved that every extension of finite fields possesses a primitive normal basis, the case when F is a prime field having been settled by Harold Davenport.

## Free elements

If K / F is a Galois extension and x in K generates a normal basis over F, then x is free in K / F. If x has the property that for every subgroup H of the Galois group G, with fixed field K$^H$, x is free for K / K$^H$, then x is said to be completely free in K / F. Every Galois extension has a completely free element.