Let F ⊂ K {\displaystyle F\subset K} be a Galois extension with Galois group G {\displaystyle G} . The classical normal basis theorem states that there is an element β ∈ K {\displaystyle \beta \in K} such that { g ( β ) : g ∈ G } {\displaystyle \{g(\beta ):g\in G\}} forms a basis of K, considered as a vector space over F. That is, any element α ∈ K {\displaystyle \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 ∈ F . {\displaystyle a_{g}\in F.}
A normal basis contrasts with a primitive element basis of the form { 1 , β , β 2 , … , β n − 1 } {\displaystyle \{1,\beta ,\beta ^{2},\ldots ,\beta ^{n-1}\}} , where β ∈ K {\displaystyle \beta \in K} is an element whose minimal polynomial has degree n = [ K : F ] {\displaystyle n=[K:F]} .
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 ϕ : F [ G ] → K {\displaystyle \phi :F[G]\rightarrow K} is of form ϕ ( r ) = r β {\displaystyle \phi (r)=r\beta } for some β ∈ K {\displaystyle \beta \in K} . Since { 1 ⋅ σ | σ ∈ G } {\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 K ≅ F [ G ] {\displaystyle K\cong F[G]} as a left F [ G ] {\displaystyle F[G]} -module. In terms of representations of G over F, this means that K is isomorphic to the regular representation.
For finite fields this can be stated as follows:[1] Let F = G F ( q ) = F q {\displaystyle F=\mathrm {GF} (q)=\mathbb {F} _{q}} denote the field of q elements, where q = pm is a prime power, and let K = G F ( q n ) = F q n {\displaystyle K=\mathrm {GF} (q^{n})=\mathbb {F} _{q^{n}}} denote its extension field of degree n ≥ 1. Here the Galois group is G = Gal ( K / F ) = { 1 , Φ , Φ 2 , … , Φ n − 1 } {\displaystyle G={\text{Gal}}(K/F)=\{1,\Phi ,\Phi ^{2},\ldots ,\Phi ^{n-1}\}} with Φ n = 1 , {\displaystyle \Phi ^{n}=1,} a cyclic group generated by the _q_-power Frobenius automorphism Φ ( α ) = α q , {\displaystyle \Phi (\alpha )=\alpha ^{q},} with Φ n = 1 = I d K . {\displaystyle \Phi ^{n}=1=\mathrm {Id} _{K}.} Then there exists an element β ∈ K such that { β , Φ ( β ) , Φ 2 ( β ) , … , Φ n − 1 ( β ) } = { β , β q , β q 2 , … , β q n − 1 } {\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.
In case the Galois group is cyclic as above, generated by Φ {\displaystyle \Phi } with Φ n = 1 , {\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 χ ( h 1 h 2 ) = χ ( h 1 ) χ ( h 2 ) {\displaystyle \chi (h_{1}h_{2})=\chi (h_{1})\chi (h_{2})} ; then any distinct characters χ 1 , χ 2 , … {\displaystyle \chi _{1},\chi _{2},\ldots } are linearly independent in the _K_-vector space of mappings. We apply this to the Galois group automorphisms χ i = Φ i : K → K , {\displaystyle \chi _{i}=\Phi ^{i}:K\to K,} thought of as mappings from the multiplicative group H = K × {\displaystyle H=K^{\times }} . Now K ≅ F n {\displaystyle K\cong F^{n}} as an F_-vector space, so we may consider Φ : F n → F n {\displaystyle \Phi :F^{n}\to F^{n}} as an element of the matrix algebra M_n(F); since its powers 1 , Φ , … , Φ n − 1 {\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 X n − 1 {\displaystyle X^{n}-1} .
The second basic fact is the classification of finitely generated modules over a PID such as F [ X ] {\displaystyle 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 ) {\displaystyle f_{i}(X)} may be chosen so that they are monic polynomials or zero and f i + 1 ( X ) {\displaystyle f_{i+1}(X)} is a multiple of f i ( X ) {\displaystyle f_{i}(X)} . f k ( 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 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 = ∞ {\displaystyle \dim _{F}M=\infty } . In our case of cyclic G of size n generated by Φ {\displaystyle \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 ⋅ Φ {\displaystyle 1\cdot \Phi } , so every F [ G ] {\displaystyle F[G]} -module may be viewed as an F [ X ] {\displaystyle F[X]} -module with multiplication by X being multiplication by 1 ⋅ Φ {\displaystyle 1\cdot \Phi } . In case of K this means X α = Φ ( α ) {\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 f k ( X ) = X n − 1 {\displaystyle f_{k}(X)=X^{n}-1} . Since dim F ( K ) = n , {\displaystyle \dim _{F}(K)=n,} we can only have k = 1 {\displaystyle 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 ] {\displaystyle F[G]} -modules K ≅ F [ G ] {\displaystyle K\cong F[G]} that we talked about above, and under it the basis { 1 , X , X 2 , … , X n − 1 } {\displaystyle \{1,X,X^{2},\ldots ,X^{n-1}\}} on the right side corresponds to a normal basis { β , Φ ( β ) , Φ 2 ( β ) , … , Φ n − 1 ( β ) } {\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.
Consider the field K = G F ( 2 3 ) = F 8 {\displaystyle K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}} over F = G F ( 2 ) = F 2 {\displaystyle F=\mathrm {GF} (2)=\mathbb {F} _{2}} , with Frobenius automorphism Φ ( α ) = α 2 {\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 X n − 1 = X 3 − 1 = ( X − 1 ) ( X 2 + X + 1 ) ∈ F [ X ] {\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): K ≅ F [ X ] ( X 3 − 1 ) ≅ F [ X ] ( X + 1 ) ⊕ F [ X ] ( X 2 + X + 1 ) . {\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 F ⊂ K {\displaystyle F\subset K} , while the second is isomorphic as an _F_[_G_]-module to F 2 2 ≅ F 2 [ X ] / ( X 2 + X + 1 ) {\displaystyle \mathbb {F} _{2^{2}}\cong \mathbb {F} _{2}[X]/(X^{2}{+}X{+}1)} under the action Φ ⋅ X i = X i + 1 . {\displaystyle \Phi \cdot X^{i}=X^{i+1}.} (Thus K ≅ F 2 ⊕ F 4 {\displaystyle K\cong \mathbb {F} _{2}\oplus \mathbb {F} _{4}} as _F_[_G_]-modules, but not as _F_-algebras.)
The elements β ∈ K {\displaystyle \beta \in K} which can be used for a normal basis are precisely those outside either of the submodules, so that ( Φ + 1 ) ( β ) ≠ 0 {\displaystyle (\Phi {+}1)(\beta )\neq 0} and ( Φ 2 + Φ + 1 ) ( β ) ≠ 0 {\displaystyle (\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 ) ( t 3 + t + 1 ) ( t 3 + t 2 + 1 ) ∈ F [ t ] , {\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 F = F 2 {\displaystyle F=\mathbb {F} _{2}} are the roots of t ( t + 1 ) {\displaystyle t(t{+}1)} , the nonzero elements of the submodule F 4 {\displaystyle \mathbb {F} _{4}} are the roots of t 3 + t + 1 {\displaystyle 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 {\displaystyle t^{3}{+}t^{2}{+}1} .
By contrast, for the extension field L = G F ( 2 4 ) = F 16 {\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 L ≅ F 2 [ X ] / ( X 4 − 1 ) = F 2 [ X ] / ( X + 1 ) 4 . {\displaystyle L\ \cong \ \mathbb {F} _{2}[X]/(X^{4}{-}1)\ =\ \mathbb {F} _{2}[X]/(X{+}1)^{4}.} Here the operator Φ ≅ X {\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 ( Φ + 1 ) 3 ( β ) ≠ 0 {\displaystyle (\Phi {+}1)^{3}(\beta )\neq 0} .
For example, in the field K = G F ( 2 3 ) = F 8 {\displaystyle K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}} above, we may represent elements as bit-strings: α = ( a 2 , a 1 , a 0 ) = a 2 Φ 2 ( β ) + a 1 Φ ( β ) + a 0 β = a 2 β 4 + a 1 β 2 + a 0 β , {\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 a i ∈ G F ( 2 ) = { 0 , 1 } . {\displaystyle a_{i}\in \mathrm {GF} (2)=\{0,1\}.} Now we can square elements by doing a left circular shift, α 2 = Φ ( a 2 , a 1 , a 0 ) = ( a 1 , a 0 , a 2 ) {\displaystyle \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.
Suppose K / F {\displaystyle K/F} is a finite Galois extension of the infinite field F. Let [K : _F_] = n, Gal ( K / F ) = G = { σ 1 . . . σ n } {\displaystyle {\text{Gal}}(K/F)=G=\{\sigma _{1}...\sigma _{n}\}} , where σ 1 = Id {\displaystyle \sigma _{1}={\text{Id}}} . By the primitive element theorem there exists α ∈ K {\displaystyle \alpha \in K} such i ≠ j ⟹ σ i ( α ) ≠ σ j ( α ) {\displaystyle i\neq j\implies \sigma _{i}(\alpha )\neq \sigma _{j}(\alpha )} and K = F [ α ] {\displaystyle K=F[\alpha ]} . Let us write α i = σ i ( α ) {\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 f ( X ) = ∏ i = 1 n ( X − α i ) {\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 g ( X ) = f ( X ) ( X − α ) f ′ ( α ) g i ( X ) = f ( X ) ( X − α i ) f ′ ( α i ) = σ i ( g ( X ) ) . {\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, g i ( X ) = ∏ 1 ≤ j ≤ n j ≠ i X − α j α i − α j g ( X ) = g 1 ( X ) . {\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 g ( α ) = 1 {\displaystyle g(\alpha )=1} and g i ( α ) = 0 {\displaystyle g_{i}(\alpha )=0} for i ≠ 1 {\displaystyle i\neq 1} . Next, define an n × n {\displaystyle n\times n} matrix A of polynomials over K and a polynomial D by A i j ( X ) = σ i ( σ j ( g ( X ) ) = σ i ( g j ( X ) ) D ( X ) = det A ( X ) . {\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 A i j ( X ) = g k ( X ) {\displaystyle A_{ij}(X)=g_{k}(X)} , where k is determined by σ k = σ i ⋅ σ j {\displaystyle \sigma _{k}=\sigma _{i}\cdot \sigma _{j}} ; in particular k = 1 {\displaystyle k=1} iff σ i = σ j − 1 {\displaystyle \sigma _{i}=\sigma _{j}^{-1}} . It follows that A ( α ) {\displaystyle A(\alpha )} is the permutation matrix corresponding to the permutation of G which sends each σ i {\displaystyle \sigma _{i}} to σ i − 1 {\displaystyle \sigma _{i}^{-1}} . (We denote by A ( α ) {\displaystyle A(\alpha )} the matrix obtained by evaluating A ( X ) {\displaystyle A(X)} at x = α {\displaystyle x=\alpha } .) Therefore, D ( α ) = det A ( α ) = ± 1 {\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 a ∈ F {\displaystyle a\in F} such that D ( a ) ≠ 0 {\displaystyle D(a)\neq 0} . Define β = g ( a ) β i = g i ( a ) = σ i ( β ) . {\displaystyle {\begin{aligned}\beta &=g(a)\\\beta _{i}&=g_{i}(a)=\sigma _{i}(\beta ).\end{aligned}}} We claim that { β 1 , … , β n } {\displaystyle \{\beta _{1},\ldots ,\beta _{n}\}} is a normal basis. We only have to show that β 1 , … , β n {\displaystyle \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 ∈ F {\displaystyle x_{1}...x_{n}\in F} . Applying the automorphism σ i {\displaystyle \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 ) ⋅ x ¯ = 0 ¯ {\displaystyle A(a)\cdot {\overline {x}}={\overline {0}}} . Since det A ( a ) = D ( a ) ≠ 0 {\displaystyle \det A(a)=D(a)\neq 0} , we conclude that x ¯ = 0 ¯ {\displaystyle {\overline {x}}={\overline {0}}} , which completes the proof.
It is tempting to take a = α {\displaystyle a=\alpha } because D ( α ) ≠ 0 {\displaystyle D(\alpha )\neq 0} . But this is impermissible because we used the fact that a ∈ F {\displaystyle a\in F} to conclude that for any _F_-automorphism σ {\displaystyle \sigma } and polynomial h ( X ) {\displaystyle h(X)} over K {\displaystyle K} the value of the polynomial σ ( h ( X ) ) {\displaystyle \sigma (h(X))} at a equals σ ( h ( a ) ) {\displaystyle \sigma (h(a))} .
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.
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 KH, x is free for K / KH, then x is said to be completely free in K / F. Every Galois extension has a completely free element.[2]
Menezes, Alfred J., ed. (1993). Applications of finite fields. The Kluwer International Series in Engineering and Computer Science. Vol. 199. Boston: Kluwer Academic Publishers. ISBN978-0792392828. Zbl0779.11059.
![{\displaystyle n=[K:F]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4e03baa87063bfd9df9f2702dea72a0a646724a)
![{\displaystyle \phi :F[G]\rightarrow K}](https://wikimedia.org/api/rest_v1/media/math/render/svg/29ec7b9bdd492fd69fa6d7ac8f257e8e0a21b867)
![{\displaystyle K\cong F[G]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cc1c792ae7f9a551591702ba830fbda92e4a07fc)
![{\displaystyle F[G]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8bf843b53d11e972a0627ad44d2a94a2c19298f)
![{\displaystyle F[X]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/26dc049157db08b423b1c6916eba0c81b1bdc18b)
![{\textstyle M\cong \bigoplus _{i=1}^{k}{\frac {F[X]}{(f_{i}(X))}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3ae4053763b8e15d04ee27a7d0fcb742505595d)
![{\textstyle F[G]\cong {\frac {F[X]}{(X^{n}-1)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a8ae1f09d5f76c05d5349009e5c43de59333137)
![{\textstyle K\cong {\frac {F[X]}{(X^{n}{-}\,1)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b0efa9bfb336a865cab98ad220e0448c5e4af78)
![{\displaystyle X^{n}-1\ =\ X^{3}-1\ =\ (X{-}1)(X^{2}{+}X{+}1)\ \in \ F[X]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dfce5ffb95d82c40855b1795cabcc39ccd407d63)
![{\displaystyle K\ \cong \ {\frac {F[X]}{(X^{3}{-}\,1)}}\ \cong \ {\frac {F[X]}{(X{+}1)}}\oplus {\frac {F[X]}{(X^{2}{+}X{+}1)}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/607508c17c6af9570c384a0269482db42df1867f)
![{\displaystyle \mathbb {F} _{2^{2}}\cong \mathbb {F} _{2}[X]/(X^{2}{+}X{+}1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2f766025556fe0abad75f81ce9c1d14d9eb33a2)
![{\displaystyle t^{2^{3}}-t\ =\ t(t{+}1)\left(t^{3}+t+1\right)\left(t^{3}+t^{2}+1\right)\ \in \ F[t],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2961e1543a2c38cc88bbd0b2d975a099d2bc354e)
![{\displaystyle L\ \cong \ \mathbb {F} _{2}[X]/(X^{4}{-}1)\ =\ \mathbb {F} _{2}[X]/(X{+}1)^{4}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cf98a4e5be183650b61a5d7e301335303dffb65)
![{\displaystyle K=F[\alpha ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f4c1b8eee4c90f687044d6b4371d85ab95d08a7)
