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$ 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.

References

↑ Nader H. Bshouty; Gadiel Seroussi (1989), Generalizations of the normal basis theorem of finite fields (PDF), p. 1; SIAM J. Discrete Math. 3 (1990), no. 3, 330–337.
↑ Dirk Hachenberger, Completely free elements, in Cohen & Niederreiter (1996) pp. 97–107 Zbl 0864.11066

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.

[1] Nader H. Bshouty; Gadiel Seroussi (1989), Generalizations of the normal basis theorem of finite fields (PDF), p. 1; SIAM J. Discrete Math. 3 (1990), no. 3, 330–337.

[2] Dirk Hachenberger, Completely free elements, in Cohen & Niederreiter (1996) pp. 97–107 Zbl 0864.11066