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 ${\displaystyle F\subset K}$ be a Galois extension with Galois group ${\displaystyle G}$. The classical normal basis theorem states that there is an element ${\displaystyle \beta \in K}$ such that ${\displaystyle \{g(\beta ):g\in G\}}$ forms a basis of K, considered as a vector space over F. That is, any element ${\displaystyle \alpha \in K}$ can be written uniquely as ${\textstyle \alpha =\sum _{g\in G}a_{g}\,g(\beta )}$ for some elements ${\displaystyle a_{g}\in F.}$

A normal basis contrasts with a primitive element basis of the form ${\displaystyle \{1,\beta ,\beta ^{2},\ldots ,\beta ^{n-1}\}}$, where ${\displaystyle \beta \in K}$ is an element whose minimal polynomial has degree ${\displaystyle 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 ${\displaystyle \phi :F[G]\rightarrow K}$ is of form ${\displaystyle \phi (r)=r\beta }$ for some ${\displaystyle \beta \in K}$. Since ${\displaystyle \{1\cdot \sigma |\sigma \in G\}}$ is a linear basis of F[G] over F, it follows easily that ${\displaystyle \phi }$ is bijective iff ${\displaystyle \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 ${\displaystyle K\cong F[G]}$ as left ${\displaystyle 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:^[1] Let ${\displaystyle F=\mathrm {GF} (q)=\mathbb {F} _{q}}$ denote the field of q elements, where q = p^m is a prime power, and let ${\displaystyle K=\mathrm {GF} (q^{n})=\mathbb {F} _{q^{n}}}$ denote its extension field of degree n ≥ 1. Here the Galois group is ${\displaystyle G={\text{Gal}}(K/F)=\{1,\Phi ,\Phi ^{2},\ldots ,\Phi ^{n-1}\}}$ with ${\displaystyle \Phi ^{n}=1,}$ a cyclic group generated by the q-power Frobenius automorphism ${\displaystyle \Phi (\alpha )=\alpha ^{q},}$with ${\displaystyle \Phi ^{n}=1=\mathrm {Id} _{K}.}$ Then there exists an element β ∈ K such that $${\displaystyle \{\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 ${\displaystyle \Phi }$ with ${\displaystyle \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 ${\displaystyle \chi (h_{1}h_{2})=\chi (h_{1})\chi (h_{2})}$; then any distinct characters ${\displaystyle \chi _{1},\chi _{2},\ldots }$ are linearly independent in the K-vector space of mappings. We apply this to the Galois group automorphisms ${\displaystyle \chi _{i}=\Phi ^{i}:K\to K,}$ thought of as mappings from the multiplicative group ${\displaystyle H=K^{\times }}$. Now ${\displaystyle K\cong F^{n}}$as an F-vector space, so we may consider ${\displaystyle \Phi :F^{n}\to F^{n}}$ as an element of the matrix algebra M_n(F); since its powers ${\displaystyle 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 ${\displaystyle X^{n}-1}$.

The second basic fact is the classification of finitely generated modules over a PID such as ${\displaystyle F[X]}$. Every such module M can be represented as ${\textstyle M\cong \bigoplus _{i=1}^{k}{\frac {F[X]}{(f_{i}(X))}}}$, where ${\displaystyle f_{i}(X)}$ may be chosen so that they are monic polynomials or zero and ${\displaystyle f_{i+1}(X)}$ is a multiple of ${\displaystyle f_{i}(X)}$. ${\displaystyle 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 ${\displaystyle \dim _{F}M=\infty }$. In our case of cyclic G of size n generated by ${\displaystyle \Phi }$ we have an F-algebra isomorphism ${\textstyle F[G]\cong {\frac {F[X]}{(X^{n}-1)}}}$ where X corresponds to ${\displaystyle 1\cdot \Phi }$, so every ${\displaystyle F[G]}$-module may be viewed as an ${\displaystyle F[X]}$-module with multiplication by X being multiplication by ${\displaystyle 1\cdot \Phi }$. In case of K this means ${\displaystyle X\alpha =\Phi (\alpha )}$, so the monic polynomial of smallest degree annihilating K is the minimal polynomial of ${\displaystyle \Phi }$. Since K is a finite dimensional F-space, the representation above is possible with ${\displaystyle f_{k}(X)=X^{n}-1}$. Since ${\displaystyle \dim _{F}(K)=n,}$ we can only have ${\displaystyle 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 ${\displaystyle F[G]}$-modules ${\displaystyle K\cong F[G]}$ that we talked about above, and under it the basis ${\displaystyle \{1,X,X^{2},\ldots ,X^{n-1}\}}$ on the right side corresponds to a normal basis ${\displaystyle \{\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 ${\displaystyle K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}}$ over ${\displaystyle F=\mathrm {GF} (2)=\mathbb {F} _{2}}$, with Frobenius automorphism ${\displaystyle \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 $${\displaystyle 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):$${\displaystyle 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 ${\displaystyle F\subset K}$, while the second is isomorphic as an F[G]-module to ${\displaystyle \mathbb {F} _{2^{2}}\cong \mathbb {F} _{2}[X]/(X^{2}{+}X{+}1)}$ under the action ${\displaystyle \Phi \cdot X^{i}=X^{i+1}.}$ (Thus ${\displaystyle K\cong \mathbb {F} _{2}\oplus \mathbb {F} _{4}}$ as F[G]-modules, but not as F-algebras.)

The elements ${\displaystyle \beta \in K}$ which can be used for a normal basis are precisely those outside either of the submodules, so that ${\displaystyle (\Phi {+}1)(\beta )\neq 0}$ and ${\displaystyle (\Phi ^{2}{+}\Phi {+}1)(\beta )\neq 0}$. In terms of the G-orbits of K, which correspond to the irreducible factors of: $${\displaystyle 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 ${\displaystyle F=\mathbb {F} _{2}}$ are the roots of ${\displaystyle t(t{+}1)}$, the nonzero elements of the submodule ${\displaystyle \mathbb {F} _{4}}$ are the roots of ${\displaystyle t^{3}+t+1}$, while the normal basis, which in this case is unique, is given by the roots of the remaining factor ${\displaystyle t^{3}{+}t^{2}{+}1}$.

By contrast, for the extension field ${\displaystyle L=\mathrm {GF} (2^{4})=\mathbb {F} _{16}}$ in which n = 4 is divisible by p = 2, we have the F[G]-module isomorphism $${\displaystyle L\ \cong \ \mathbb {F} _{2}[X]/(X^{4}{-}1)\ =\ \mathbb {F} _{2}[X]/(X{+}1)^{4}.}$$ Here the operator ${\displaystyle \Phi \cong X}$ is not diagonalizable, the module L has nested submodules given by generalized eigenspaces of ${\displaystyle \Phi }$, and the normal basis elements β are those outside the largest proper generalized eigenspace, the elements with ${\displaystyle (\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 ${\displaystyle K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}}$ above, we may represent elements as bit-strings: $${\displaystyle \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 ${\displaystyle a_{i}\in \mathrm {GF} (2)=\{0,1\}.}$ Now we can square elements by doing a left circular shift, ${\displaystyle \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 ${\displaystyle K/F}$ is a finite Galois extension of the infinite field F. Let [K : F] = n, ${\displaystyle {\text{Gal}}(K/F)=G=\{\sigma _{1}...\sigma _{n}\}}$, where ${\displaystyle \sigma _{1}={\text{Id}}}$. By the primitive element theorem there exists ${\displaystyle \alpha \in K}$ such ${\displaystyle i\neq j\implies \sigma _{i}(\alpha )\neq \sigma _{j}(\alpha )}$ and ${\displaystyle K=F[\alpha ]}$. Let us write ${\displaystyle \alpha _{i}=\sigma _{i}(\alpha )}$. ${\displaystyle \alpha }$'s (monic) minimal polynomial f over K is the irreducible degree n polynomial given by the formula $${\displaystyle {\begin{aligned}f(X)&=\prod _{i=1}^{n}(X-\alpha _{i})\end{aligned}}}$$ Since f is separable (it has simple roots) we may define $${\displaystyle {\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, $${\displaystyle {\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 ${\displaystyle g(\alpha )=1}$ and ${\displaystyle g_{i}(\alpha )=0}$ for ${\displaystyle i\neq 1}$. Next, define an ${\displaystyle n\times n}$ matrix A of polynomials over K and a polynomial D by $${\displaystyle {\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 ${\displaystyle A_{ij}(X)=g_{k}(X)}$, where k is determined by ${\displaystyle \sigma _{k}=\sigma _{i}\cdot \sigma _{j}}$; in particular ${\displaystyle k=1}$ iff ${\displaystyle \sigma _{i}=\sigma _{j}^{-1}}$. It follows that ${\displaystyle A(\alpha )}$ is the permutation matrix corresponding to the permutation of G which sends each ${\displaystyle \sigma _{i}}$ to ${\displaystyle \sigma _{i}^{-1}}$. (We denote by ${\displaystyle A(\alpha )}$ the matrix obtained by evaluating ${\displaystyle A(X)}$ at ${\displaystyle x=\alpha }$.) Therefore, ${\displaystyle 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 ${\displaystyle a\in F}$ such that ${\displaystyle D(a)\neq 0}$. Define $${\displaystyle {\begin{aligned}\beta &=g(a)\\\beta _{i}&=g_{i}(a)=\sigma _{i}(\beta ).\end{aligned}}}$$ We claim that ${\displaystyle \{\beta _{1},\ldots ,\beta _{n}\}}$ is a normal basis. We only have to show that ${\displaystyle \beta _{1},\ldots ,\beta _{n}}$ are linearly independent over F, so suppose ${\textstyle \sum _{j=1}^{n}x_{j}\beta _{j}=0}$ for some ${\displaystyle x_{1}...x_{n}\in F}$. Applying the automorphism ${\displaystyle \sigma _{i}}$ yields ${\textstyle \sum _{j=1}^{n}x_{j}\sigma _{i}(g_{j}(a))=0}$ for all i. In other words, ${\displaystyle A(a)\cdot {\overline {x}}={\overline {0}}}$. Since ${\displaystyle \det A(a)=D(a)\neq 0}$, we conclude that ${\displaystyle {\overline {x}}={\overline {0}}}$, which completes the proof.

It is tempting to take ${\displaystyle a=\alpha }$ because ${\displaystyle D(\alpha )\neq 0}$. But this is impermissible because we used the fact that ${\displaystyle a\in F}$ to conclude that for any F-automorphism ${\displaystyle \sigma }$ and polynomial ${\displaystyle h(X)}$ over ${\displaystyle K}$ the value of the polynomial ${\displaystyle \sigma (h(X))}$ at a equals ${\displaystyle \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.^[2]

See also

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

References

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

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