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 ${\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 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 ${\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 ${\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 ${\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 ${\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 β⁴ gives β⁸ = β. 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 ${\textstyle \sum _{j=1}^{n}x_{j}\beta _{j}=0}$ for some $x_{1}...x_{n}\in F$. Applying the automorphism $\sigma _{i}$ yields ${\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.

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.