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.

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 = p^m 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} .

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 β⁴ gives β⁸ = β. 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 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]

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

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