Normal basis explained

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\subset 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 \{g(\beta) : g\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 $\backslash alpha\; =\; \backslash sum\_\; a\_g\backslash ,\; g(\backslash beta)$ for some elements a _{g\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 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

\phi:F[G] → K is of form \phi(r) = r\beta for some \beta \in K . Since \{ 1 ⋅ \sigma| \sigma \in G\} is a linear basis of F[''G''] over F, it follows easily 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 is finite Galois extension, then K \cong F[G] as left 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

F = GF (q) = F _{q} denote the field of q elements, where is a prime power, and let K = GF (q ^{n) = F} _{q ^{n}} denote its extension field of degree . Here the Galois group is G = 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 = Id _{K.} Then there exists an element such that$$\backslash \backslash \; =\; \backslash \; \backslash$$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 χ from a group H to a field K satisfying \chi(h _{1h} _{2)=\chi(h} _{1)\chi(h} _{2)} ; then any distinct characters \chi _{1,\chi} _{2,\ldots} are linearly independent in the K-vector space of mappings. We apply this to the Galois group automorphisms \chi ^{i:} _{i = \Phi} K \to K, thought of as mappings from the multiplicative group H = K ^{x} . Now K\cong F ^{n} as an F-vector space, so we may consider \Phi : F ^{n\to} F ^{n} as an element of the matrix algebra M_n(F); since its powers 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} .

The second basic fact is the classification of finitely generated modules over a PID such as

F[X] . Every such module M can be represented as $M\; \backslash cong\backslash bigoplus\_^k\; \backslash frac$, where f _{i(X)} may be chosen so that they are monic polynomials or zero and f _{i+1} (X) is a multiple of f _{i(X)} . 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 $\backslash dim\_F\; M\; =\; \backslash sum\_^k\; \backslash deg\; f\_i$, in the second case \dim _{F} M = inf ty . In our case of cyclic G of size n generated by \Phi we have an F-algebra isomorphism $F[G]\backslash cong\; \backslash frac$ where X corresponds to 1 ⋅ \Phi , so every F[G] -module may be viewed as an F[X] -module with multiplication by X being multiplication by 1 ⋅ \Phi . In case of K this means X\alpha = \Phi(\alpha) , so the monic polynomial of smallest degree annihilating K is the minimal polynomial of \Phi . Since K is a finite dimensional F-space, the representation above is possible with f ^{n -1} _{k(X) = X} . Since \dim _{F(K)} = n, we can only have k =1 , and $K\; \backslash cong\; \backslash frac$ 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] -modules K\cong F[G] that we talked about above, and under it the basis \{ 1 ,X,X ^{2,\ldots,X} ^{n-1} \} on the right side corresponds 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 the case of a cyclic Kummer extension.

Example

Consider the field

K = GF ( 2 ^{3 ) = F} _{8} over F = GF ( 2 ) = 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\; \backslash \; =\backslash \; X^3-1\backslash \; =\; \backslash \; (X1)(X^2X1)\; \backslash \; \backslash in\backslash \; F[X]$$ means we have a direct sum of F[''G'']-modules (by the Chinese remainder theorem):$$K\backslash \; \backslash cong\backslash \; \backslash frac\; \backslash \; \backslash cong\backslash \; \backslash frac\; \backslash oplus\; \backslash frac.$$The first component is just F\subset K , while the second is isomorphic as an F[''G'']-module to F _{2 ^{2}} \cong F ^{2 { + }X{ + } 1 )} _{2 [X]/(X} under the action \Phi ⋅ X ^{i} = X ^{i+1} . (Thus K \cong F _{2 ⊕} F _{4} as F[''G'']-modules, but not as F-algebras.)

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) ≠ 0 and (\Phi ^{2{+}\Phi{+}1)(\beta) ≠} 0 . In terms of the G-orbits of K, which correspond to the irreducible factors of:$$t^-t\; \backslash \; =\; \backslash \; t(t1)\backslash left(t^3\; +\; t\; +\; 1\backslash right)\backslash left(t^3\; +\; t^2\; +\; 1\backslash right)\backslash \; \backslash in\backslash \; F[t],$$the elements of F = F _{2} are the roots of t(t{ + } 1 ) , the nonzero elements of the submodule 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 = GF ( 2 ^{4 ) = F} _{16} in which is divisible by, we have the F[''G'']-module isomorphism $$L\; \backslash \; \backslash cong\backslash \; \backslash mathbb\_2[X]/(X^41)\backslash \; =\backslash \; \backslash mathbb\_2[X]/(X1)^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) ≠} 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 = GF ( 2 ^{3 ) = F} _{8} above, we may represent elements as bit-strings:$$\backslash alpha\; \backslash \; =\backslash \; (a\_2,a\_1,a\_0)\backslash \; =\backslash \; a\_2\backslash Phi^2(\backslash beta)\; +\; a\_1\backslash Phi(\backslash beta)+a\_0\backslash beta\backslash \; =\backslash \; a\_2\backslash beta^4\; +\; a\_1\backslash beta^2\; +a\_0\backslash beta,$$where the coefficients are bits a _{i\in} 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.

Proof for the case of infinite fields

Suppose

K/F is a finite Galois extension of the infinite field F. Let, Gal (K/F) = G = \{\sigma _{1...\sigma} _{n\}} , where \sigma _{1} = Id . By the primitive element theorem there exists \alpha \in K such i\ne j\implies \sigma _{i(\alpha)\ne\sigma} _{j(\alpha)} and K = F[\alpha] . Let us write \alpha _{i} = \sigma _{i(\alpha)} . \alpha 's (monic) minimal polynomial f over K is the irreducible degree n polynomial given by the formulaSince f is separable (it has simple roots) we may define In other words,Note that g(\alpha) =1 and g _{i(\alpha)=0} for i \ne 1 . Next, define an n x n matrix A of polynomials over K and a polynomial D byObserve that A _{ij} (X) = g _{k(X)} , where k is determined by \sigma _{k} = \sigma _{i} ⋅ \sigma _{j} ; in particular k =1 iff \sigma _{i} = \sigma ^{-1} _{j} . It follows that A(\alpha) is the permutation matrix corresponding to the permutation of G which sends each \sigma _{i} to \sigma ^{-1} _{i} . (We denote by A(\alpha) the matrix obtained by evaluating A(X) at x = \alpha .) Therefore, 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\in F such that D(a)\ne 0 . DefineWe claim that \{\beta _{1,} \ldots, \beta _{n\}} is a normal basis. We only have to show that \beta _{1,} \ldots,\beta _{n} are linearly independent over F, so suppose $\backslash sum\_^n\; x\_j\; \backslash beta\_j\; =\; 0$ for some x _{1...x} _{n\in} F . Applying the automorphism \sigma _{i} yields $\backslash sum\_^n\; x\_j\; \backslash sigma\_i(g\_j(a))\; =\; 0$ for all i. In other words, A(a) ⋅ \overline {x} = \overline { 0 } . Since \det A(a) = D(a) \ne 0 , we conclude that \overline x = \overline 0 , which completes the proof.

It is tempting to take

a = \alpha because D(\alpha) ≠ 0 . But this is impermissible because we used the fact that a \in F to conclude that for any F-automorphism \sigma and polynomial h(X) over K the value of the polynomial \sigma(h(X)) at a equals \sigma(h(a)) .

Primitive normal basis

A primitive normal basis of an extension of finite fields is a normal basis for 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 finite field extension possesses a primitive normal basis, the case when F is a prime field having been settled by Harold Davenport.

Free elements

If is a Galois extension and x in K generates a normal basis over F, then x is free in . If x has the property that for every subgroup H of the Galois group G, with fixed field K^H, x is free for, then x is said to be completely free in . Every Galois extension has a completely free element.^[2]

See also

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

References

• Book: S. . Cohen . H. . Niederreiter. Harald Niederreiter . Finite Fields and Applications. Proceedings of the 3rd international conference, Glasgow, UK, July 11–14, 1995 . . 978-0-521-56736-7 . 1996 . London Mathematical Society Lecture Note Series . 233 . 0851.00052 .
• Lenstra . H.W. Jr . Hendrik Lenstra . Schoof . R.J. . René Schoof . Primitive normal bases for finite fields . 0615.12023 . . 48 . 177 . 217–231 . 1987 . 2007886 . 10.2307/2007886. free . 1887/3824 . free .
• Book: Menezes . Alfred J. . Alfred Menezes . Applications of finite fields . 0779.11059 . The Kluwer International Series in Engineering and Computer Science . 199 . Boston . Kluwer Academic Publishers . 1993 . 978-0792392828 .

Notes and References

1. SIAM J. Discrete Math. 3 (1990), no. 3, 330–337.

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