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\subseteq 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 $\{\sigma (\beta ):\sigma \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 ${\textstyle \alpha =\sum _{\sigma \in G}a_{\sigma }\,\sigma (\beta )}$ for some coefficients $a_{\sigma }\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; thus K is also a left module for the group algebra F[G]. Every homomorphism of left F[G]-modules $\phi :F[G]\rightarrow K$ is of form $\phi (\sigma )=\sigma (\beta )$ for some $\beta \in K$. Since ${\displaystyle \{\sigma$ :\sigma \in G\}} is a linear basis of F[G] over F, we see 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: K is isomorphic to the regular representation. Also, a given $\beta$ generates a normal basis iff, when considering K as a G-representation, $\beta$ does not lie in any proper subrepresentation.

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 $\chi$ from a group $H$ to a field $K$ satisfying $\chi (h_{1}h_{2})=\chi (h_{1})\chi (h_{2})$ and $\chi (1)=1$; then any distinct characters $\chi _{1},\chi _{2},\ldots$ are linearly independent in the $K$-vector space of mappings $H\to K$. 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 $M_{n}(F)\subset M_{n}(K)$; since its powers $1,\Phi ,\ldots ,\Phi ^{n-1}$ are linearly independent over $K$ in $M_{n}(K)$ and a fortiori over $F$ in $M_{n}(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 modules over a PID such as $F[X]$. Every such module $M$ of finite dimension over F can be represented as ${\textstyle M\cong \bigoplus _{i=1}^{k}{\frac {F[X]}{(f_{i}(X))}}}$, where $f_{i}(X)$ are monic polynomials and $f_{i+1}(X)$ is a multiple of $f_{i}(X)$, so that the highest $f_{k}(X)$ is the monic polynomial of smallest degree annihilating the module. For our cyclic Galois group $G$ of order n, we have an $F$-algebra isomorphism ${\textstyle F[G]\cong {\frac {F[X]}{(X^{n}-1)}}}$ taking the generator $\Phi$ to the variable $X$: this makes every $F[G]$-module into an $F[X]$-module. Consider $M=K$ as an $F[X]$-module under $X\alpha =\Phi (\alpha )$: the minimal monic polynomial $f_{k}(X)$ annihilating $M$ is the minimal polynomial of $\Phi$, namely $f_{k}(X)=X^{n}-1$. Since $\dim _{F}(M)=n,$ we can only have $k=1$, and ${\textstyle K\cong {\frac {F[X]}{(X^{n}{-}\,1)}}}$ as $F[X]$-modules (but this is not an isomorphism of rings). Thus we have an isomorphism of $F[G]$-modules

${\textstyle K\cong {\frac {F[X]}{(X^{n}{-}\,1)}}\cong F[G]}$,

under which the basis $\{1,X,X^{2},\ldots ,X^{n-1}\}$ corresponds to the basis $\{1,\Phi ,\Phi ^{2},\ldots ,\Phi ^{n-1}\}$ of $F[G]$ on the right side, and 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 characteristic zero for 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 rings.)

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 in: $$t^{8}-t\ =\ t(t{+}1)\left(t^{3}+t+1\right)\left(t^{3}+t^{2}+1\right)\ \in \ F[t],$$ the elements of the submodule $F=\mathbb {F} _{2}$ are the roots of $t(t{+}1)$; and 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 β⁴ gives β⁸ = β. This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring.

Primitive normal basis

A primitive normal basis of an extension of finite fields $K/F$ is a normal basis that is generated by a primitive element of $K$, that is a generator of the multiplicative group $K^{\times }$. (Note that this is a stronger definition of primitive element than mentioned above: 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.

Proof for the case of infinite fields

Suppose $K/F$ is a finite Galois extension of the infinite field F. Let $n=[K:F]$, $G={\text{Gal}}(K/F)=\{\sigma _{1}...\sigma _{n}\}$ with $\sigma _{1}={\text{Id}}$. By the primitive element theorem there exists $\alpha \in K$ such that $K=F[\alpha ]$ and $\sigma _{i}(\alpha )\neq \sigma _{j}(\alpha )$ for $i\neq j$; and write $\alpha _{i}=\sigma _{i}(\alpha )$. The minimal polynomial f of $\alpha$ over K is:$$f(X)=\prod _{i=1}^{n}(X-\alpha _{i}),$$a degree n monic polynomial which is irreducible in $K[X]$. Since f is separable (having simple roots) we may define the Lagrange interpolation polynomials $g_{1}(X),\ldots ,g_{n}(X)$ satisfying $g_{i}(\alpha _{i})=1$ and $g_{i}(\alpha _{j})=0$ for $i\neq j$:$${\begin{aligned}g(X)&=\ {\frac {f(X)}{(X-\alpha )f'(\alpha )}}\ =\ \prod _{\begin{array}{c}1\leq j\leq n\\j\neq i\end{array}}{\frac {X-\alpha _{j}}{\alpha -\alpha _{j}}},\\g_{i}(X)&=\ \sigma _{i}(g(X))\ =\ {\frac {f(X)}{(X-\alpha _{i})f'(\alpha _{i})}}\ =\ \prod _{\begin{array}{c}1\leq j\leq n\\j\neq i\end{array}}{\frac {X-\alpha _{j}}{\alpha _{i}-\alpha _{j}}}.\end{aligned}}$$Next, define an $n\times n$ matrix of polynomials $A=(A_{ij}(X))$ by$$A_{ij}(X)=\sigma _{i}(\sigma _{j}(g(X))=\sigma _{i}(g_{j}(X)),$$and let $D(X)=\det A(X)$. To see this a non-zero polynomial, observe that $A_{ij}(X)=g_{k}(X)$, where k is determined by $\sigma _{k}=\sigma _{i}\cdot \sigma _{j}$, and $k=1$ iff $\sigma _{i}=\sigma _{j}^{-1}$; thus $A(\alpha )$ is the permutation matrix corresponding to the permutation of G which sends each $\sigma _{i}$ to $\sigma _{i}^{-1}$, and $D(\alpha )=\det A(\alpha )=\pm 1$. Since $D(X)$ is a non-zero polynomial, it has only a finite number of roots; and since we assumed F is infinite, we can find $a\in F$ with $D(a)\neq 0$. Define $$\beta =g(a),\qquad \beta _{i}=g_{i}(a)=\sigma _{i}(\beta ).$$ We claim that $\{\beta _{1},\ldots ,\beta _{n}\}$ is a normal basis; i.e. that $\beta _{1},\ldots ,\beta _{n}$ are linearly independent over F. Suppose ${\textstyle \sum _{j=1}^{n}c_{j}\beta _{j}=0}$ for some ${\vec {c}}=(c_{1},...,c_{n})\in F^{n}$; applying any $\sigma _{i}$ gives ${\textstyle \sum _{j=1}^{n}c_{j}\sigma _{i}(g_{j}(a))=0}$, so that $A(a)\cdot {\vec {c}}={\vec {0}}$. Since $\det A(a)=D(a)\neq 0$, we conclude that ${\vec {c}}={\vec {0}}$, which completes the proof.

It is tempting to take $a=\alpha$ because $D(\alpha )\neq 0$, but we need $a\in F$ to conclude that $\sigma _{i}(g_{j}(a))=\sigma _{i}(g_{j}(X))|_{X=\sigma _{i}(a)}=\sigma _{i}(g_{j}(X))|_{X=a}$ is a matrix entry of $A(a)=A(X)|_{x=a}$.

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.

See also

• Dual basis in a field extension
• Polynomial basis
• Zech's logarithm

References

• Cohen, S.; Niederreiter, H., eds. (1996). Finite Fields and Applications. Proceedings of the 3rd international conference, Glasgow, UK, July 11–14, 1995. London Mathematical Society Lecture Note Series. Vol. 233. Cambridge University Press. ISBN 978-0-521-56736-7. Zbl 0851.00052.
• Lenstra, H.W. Jr; Schoof, R.J. (1987). "Primitive normal bases for finite fields". Mathematics of Computation. 48 (177): 217–231. doi:10.2307/2007886. hdl:1887/3824. JSTOR 2007886. Zbl 0615.12023.
• Menezes, Alfred J., ed. (1993). Applications of finite fields. The Kluwer International Series in Engineering and Computer Science. Vol. 199. Boston: Kluwer Academic Publishers. ISBN 978-0792392828. Zbl 0779.11059.