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 ⊆ K {\displaystyle F\subseteq 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 } {\displaystyle \{\sigma (\beta ):\sigma \in G\}} forms a basis of K {\displaystyle K}, considered as a vector space over F {\displaystyle F}. That is, any element α ∈ K {\displaystyle \alpha \in K} can be written uniquely as α = ∑ σ ∈ G a σ σ ( β ) {\textstyle \alpha =\sum _{\sigma \in G}a_{\sigma }\,\sigma (\beta )} for some coefficients a σ ∈ F {\displaystyle a_{\sigma }\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]}.

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 ϕ : F [ G ] → K {\displaystyle \phi :F[G]\rightarrow K} is of form ϕ ( σ ) = σ ( β ) {\displaystyle \phi (\sigma )=\sigma (\beta )} for some β ∈ K {\displaystyle \beta \in K}. Since { σ : σ ∈ G } {\displaystyle \{\sigma:\sigma \in G\}} is a linear basis of F[G] over F, we see 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: K is isomorphic to the regular representation. Also, a given β {\displaystyle \beta } generates a normal basis iff, when considering K as a G-representation, β {\displaystyle \beta } does not lie in any proper subrepresentation.

Case of finite fields

For finite fields this can be stated as follows: 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.

Proof for finite fields

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

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

under which the basis { 1 , X , X 2 , … , X n − 1 } {\displaystyle \{1,X,X^{2},\ldots ,X^{n-1}\}} corresponds to the basis { 1 , Φ , Φ 2 , … , Φ n − 1 } {\displaystyle \{1,\Phi ,\Phi ^{2},\ldots ,\Phi ^{n-1}\}} of F [ G ] {\displaystyle F[G]} on the right side, and to a normal basis { β , Φ ( β ) , Φ 2 ( β ) , … , Φ n − 1 ( β ) } {\displaystyle \{\beta ,\Phi (\beta ),\Phi ^{2}(\beta ),\ldots ,\Phi ^{n-1}(\beta )\}} of K {\displaystyle K} on the left.

Note that this proof would also apply in characteristic zero for a cyclic Kummer extension.

Example

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 ] {\displaystyle 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 ] {\displaystyle 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 ] {\displaystyle F[G]}-modules, but not as rings.)

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 {\displaystyle G}-orbits of K {\displaystyle K}, which correspond to the irreducible factors in: t 8 − t = t ( t + 1 ) ( t 3 + t + 1 ) ( t 3 + t 2 + 1 ) ∈ F [ t ] , {\displaystyle 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 = F 2 {\displaystyle F=\mathbb {F} _{2}} are the roots of t ( t + 1 ) {\displaystyle t(t{+}1)}; and 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 ] {\displaystyle 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 {\displaystyle 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}.

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

Primitive normal basis

A primitive normal basis of an extension of finite fields K / F {\displaystyle K/F} is a normal basis that is generated by a primitive element of K {\displaystyle K}, that is a generator of the multiplicative group K × {\displaystyle 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 {\displaystyle 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 {\displaystyle F} is a prime field having been settled by Harold Davenport.

Proof for the case of infinite fields

Suppose K / F {\displaystyle K/F} is a finite Galois extension of the infinite field F. Let n = [ K : F ] {\displaystyle n=[K:F]}, G = Gal ( K / F ) = { σ 1 . . . σ n } {\displaystyle G={\text{Gal}}(K/F)=\{\sigma _{1}...\sigma _{n}\}} with σ 1 = Id {\displaystyle \sigma _{1}={\text{Id}}}. By the primitive element theorem there exists α ∈ K {\displaystyle \alpha \in K} such that K = F [ α ] {\displaystyle K=F[\alpha ]} and σ i ( α ) ≠ σ j ( α ) {\displaystyle \sigma _{i}(\alpha )\neq \sigma _{j}(\alpha )} for i ≠ j {\displaystyle i\neq j}; and write α i = σ i ( α ) {\displaystyle \alpha _{i}=\sigma _{i}(\alpha )}. The minimal polynomial f of α {\displaystyle \alpha } over K is:f ( X ) = ∏ i = 1 n ( X − α i ) , {\displaystyle f(X)=\prod _{i=1}^{n}(X-\alpha _{i}),}a degree n monic polynomial which is irreducible in K [ X ] {\displaystyle K[X]}. Since f is separable (having simple roots) we may define the Lagrange interpolation polynomials g 1 ( X ) , … , g n ( X ) {\displaystyle g_{1}(X),\ldots ,g_{n}(X)} satisfying g i ( α i ) = 1 {\displaystyle g_{i}(\alpha _{i})=1} and g i ( α j ) = 0 {\displaystyle g_{i}(\alpha _{j})=0} for i ≠ j {\displaystyle i\neq j}:g ( X ) = f ( X ) ( X − α ) f ′ ( α ) = ∏ 1 ≤ j ≤ n j ≠ i X − α j α − α j , g i ( X ) = σ i ( g ( X ) ) = f ( X ) ( X − α i ) f ′ ( α i ) = ∏ 1 ≤ j ≤ n j ≠ i X − α j α i − α j . {\displaystyle {\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 × n {\displaystyle n\times n} matrix of polynomials A = ( A i j ( X ) ) {\displaystyle A=(A_{ij}(X))} byA i j ( X ) = σ i ( σ j ( g ( X ) ) = σ i ( g j ( X ) ) , {\displaystyle A_{ij}(X)=\sigma _{i}(\sigma _{j}(g(X))=\sigma _{i}(g_{j}(X)),}and let D ( X ) = det A ( X ) {\displaystyle D(X)=\det A(X)}. To see this a non-zero polynomial, 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}}, and k = 1 {\displaystyle k=1} iff σ i = σ j − 1 {\displaystyle \sigma _{i}=\sigma _{j}^{-1}}; thus 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}}, and D ( α ) = det A ( α ) = ± 1 {\displaystyle D(\alpha )=\det A(\alpha )=\pm 1}. Since D ( X ) {\displaystyle 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 ∈ F {\displaystyle a\in F} with D ( a ) ≠ 0 {\displaystyle D(a)\neq 0}. Define β = g ( a ) , β i = g i ( a ) = σ i ( β ) . {\displaystyle \beta =g(a),\qquad \beta _{i}=g_{i}(a)=\sigma _{i}(\beta ).} We claim that { β 1 , … , β n } {\displaystyle \{\beta _{1},\ldots ,\beta _{n}\}} is a normal basis; i.e. that β 1 , … , β n {\displaystyle \beta _{1},\ldots ,\beta _{n}} are linearly independent over F. Suppose ∑ j = 1 n c j β j = 0 {\textstyle \sum _{j=1}^{n}c_{j}\beta _{j}=0} for some c → = ( c 1 , . . . , c n ) ∈ F n {\displaystyle {\vec {c}}=(c_{1},...,c_{n})\in F^{n}}; applying any σ i {\displaystyle \sigma _{i}} gives ∑ j = 1 n c j σ i ( g j ( a ) ) = 0 {\textstyle \sum _{j=1}^{n}c_{j}\sigma _{i}(g_{j}(a))=0}, so that A ( a ) ⋅ c → = 0 → {\displaystyle A(a)\cdot {\vec {c}}={\vec {0}}}. Since det A ( a ) = D ( a ) ≠ 0 {\displaystyle \det A(a)=D(a)\neq 0}, we conclude that c → = 0 → {\displaystyle {\vec {c}}={\vec {0}}}, which completes the proof.

It is tempting to take a = α {\displaystyle a=\alpha } because D ( α ) ≠ 0 {\displaystyle D(\alpha )\neq 0}, but we need a ∈ F {\displaystyle a\in F} to conclude that σ i ( g j ( a ) ) = σ i ( g j ( X ) ) | X = σ i ( a ) = σ i ( g j ( X ) ) | X = a {\displaystyle \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 {\displaystyle 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 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.

See also