# Normal basis > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Normal_basis > Markdown URL: https://mediated.wiki/source/Normal_basis.md > Source: https://en.wikipedia.org/wiki/Normal_basis > Source revision: 1345532929 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) In [mathematics](/source/Mathematics), specifically the [algebraic](/source/Abstract_algebra) theory of [fields](/source/Field_theory_(mathematics)), a **normal basis** is a special kind of [basis](/source/Basis_(linear_algebra)) for [Galois extensions](/source/Galois_extension) of finite degree, characterised as forming a single [orbit](/source/Orbit_(group_theory)) for the [Galois group](/source/Galois_group). The **normal basis theorem** states that any finite Galois extension of fields has a normal basis. In [algebraic number theory](/source/Algebraic_number_theory), the study of the more refined question of the existence of a [normal integral basis](/source/Normal_integral_basis) is part of [Galois module](/source/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](/source/Vector_space) over *F*. That is, any element \alpha \in K can be written uniquely as \alpha = \sum_{g\in G} a_g\, g(\beta) for some elements a_g\in F. A normal basis contrasts with a [primitive element](/source/Primitive_element_theorem) 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 *K* / *F* with Galois group *G* can be naturally viewed as a [representation](/source/Group_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](/source/Group_ring) *F*[*G*]. Every homomorphism of left *F*[*G*]-modules \phi:F[G]\rightarrow K is of form \phi(r) = r\beta for some \beta \in K. Since \{1\cdot \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 *K* / *F* is finite Galois extension, then K \cong F[G] as a left F[G]-module. In terms of representations of *G* over *F*, this means that *K* is isomorphic to the [regular representation](/source/Regular_representation). ## Case of finite fields For [finite fields](/source/Finite_field) this can be stated as follows:[1] Let F = \mathrm{GF}(q)=\mathbb{F}_q denote the field of *q* elements, where *q* = *p**m* is a [prime power](/source/Prime_power), and let K= \mathrm{GF}(q^n)=\mathbb{F}_{q^n} denote its extension field of degree *n* ≥ 1. Here the Galois group is G = \text{Gal}(K/F) = \{1,\Phi,\Phi^2,\ldots,\Phi^{n-1}\} with \Phi^n = 1, a [cyclic group](/source/Cyclic_group) generated by the *q*-power [Frobenius automorphism](/source/Frobenius_endomorphism) \Phi(\alpha)=\alpha^q,with \Phi^n = 1 =\mathrm{Id}_K. Then there exists an element *β* ∈ *K* such that \{\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 \Phi with \Phi^n=1, the normal basis theorem follows from two basic facts. The first is the [linear independence](/source/Linear_independence) of characters: a *[multiplicative character](/source/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=\Phi^i: K \to K, thought of as mappings from the multiplicative group H=K^\times. Now K\cong F^nas 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](/source/Minimal_polynomial_(field_theory)) 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](/source/Modules_over_a_pid) such as F[X]. Every such module *M* can be represented as M \cong\bigoplus_{i=1}^k \frac{F[X]}{(f_i(X))}, 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](/source/Monic_polynomial) of smallest degree annihilating the module, or zero if no such non-zero polynomial exists. In the first case \dim_F M = \sum_{i=1}^k \deg f_i, in the second case \dim_F M = \infty. In our case of cyclic *G* of size *n* generated by \Phi we have an *F*-algebra isomorphism F[G]\cong \frac {F[X]}{(X^n-1)} where *X* corresponds to 1 \cdot \Phi, so every F[G]-module may be viewed as an F[X]-module with multiplication by *X* being multiplication by 1\cdot\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_k(X)=X^n-1. Since \dim_F(K) = n, we can only have k=1, and 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]-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](/source/Kummer_theory). ### Example Consider the field K=\mathrm{GF}(2^3)=\mathbb{F}_{8} over F=\mathrm{GF}(2)=\mathbb{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 \ =\ 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](/source/Chinese_remainder_theorem)): 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\subset K, while the second is isomorphic as an *F*[*G*]-module to \mathbb{F}_{2^2} \cong \mathbb{F}_2[X]/(X^2{+}X{+}1) under the action \Phi\cdot X^i = X^{i+1}. (Thus K \cong \mathbb F_2\oplus \mathbb 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)\neq 0 and (\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)\left(t^3 + t + 1\right)\left(t^3 + t^2 + 1\right)\ \in\ F[t], the elements of F=\mathbb{F}_2 are the roots of t(t{+}1), the nonzero elements of the submodule \mathbb{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 = \mathrm{GF}(2^4)=\mathbb{F}_{16} in which *n* = 4 is divisible by *p* = 2, we have the *F*[*G*]-module isomorphism L \ \cong\ \mathbb{F}_2[X]/(X^4{-}1)\ =\ \mathbb{F}_2[X]/(X{+}1)^4. Here the operator \Phi\cong X is not [diagonalizable](/source/Diagonalizable_matrix), the module *L* has nested submodules given by [generalized eigenspaces](/source/Generalized_eigenvector) of \Phi, and the normal basis elements *β* are those outside the largest proper generalized eigenspace, the elements with (\Phi{+}1)^3(\beta)\neq 0. ### Application to cryptography The normal basis is frequently used in [cryptographic](/source/Cryptography) applications based on the [discrete logarithm problem](/source/Discrete_logarithm_problem), such as [elliptic curve cryptography](/source/Elliptic_curve_cryptography), since arithmetic using a normal basis is typically more computationally efficient than using other bases. For example, in the field K=\mathrm{GF}(2^3)=\mathbb{F}_{8} above, we may represent elements as bit-strings: \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\in \mathrm{GF}(2)=\{0,1\}. Now we can square elements by doing a left [circular shift](/source/Circular_shift), \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. ## Proof for the case of infinite fields Suppose K/F is a finite Galois extension of the infinite field *F*. Let [*K* : *F*] = *n*, \text{Gal}(K/F) = G =\{\sigma_1...\sigma_n\}, where \sigma_1 = \text{Id}. By the [primitive element theorem](/source/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 formula \begin {align} f(X) &= \prod_{i=1}^n(X - \alpha_i) \end {align} Since *f* is separable (it has simple roots) we may define \begin {align} 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 {align} In other words, \begin {align} g_i(X)&= \prod_{\begin {array}{c}1 \le j \le n \\ j\ne i\end {array}}\frac{X-\alpha_j}{\alpha_i - \alpha_j}\\ g(X)&= g_1(X). \end {align} Note that g(\alpha)=1 and g_i(\alpha)=0 for i \ne 1. Next, define an n \times n matrix *A* of polynomials over *K* and a polynomial *D* by \begin {align} A_{ij}(X) &= \sigma_i(\sigma_j(g(X)) = \sigma_i(g_j(X))\\ D(X) &= \det A(X). \end {align} Observe that A_{ij}(X) = g_k(X), where *k* is determined by \sigma_k = \sigma_i \cdot \sigma_j; in particular k=1 iff \sigma_i = \sigma_j^{-1}. It follows that A(\alpha) is the [permutation matrix](/source/Permutation_matrix) corresponding to the permutation of *G* which sends each \sigma_i to \sigma_i^{-1}. (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. Define \begin {align} \beta &= g(a) \\ \beta_i &= g_i(a) = \sigma_i(\beta). \end {align} We 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 \sum_{j=1}^n x_j \beta_j = 0 for some x_1...x_n\in F. Applying the automorphism \sigma_i yields \sum_{j=1}^n x_j \sigma_i(g_j(a)) = 0 for all *i*. In other words, A(a) \cdot \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)\neq0. 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 *E* / *F* is a normal basis for *E* / *F* that is generated by a [primitive element](/source/Primitive_element_(finite_field)) 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](/source/Prime_field) having been settled by [Harold Davenport](/source/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](/source/Dual_basis_in_a_field_extension) - [Polynomial basis](/source/Polynomial_basis) - [Zech's logarithm](/source/Zech's_logarithm) ## References 1. Nader H. Bshouty & Gadiel Seroussi (1989), ["Generalizations of the normal basis theorem of finite fields"](https://hotcrp-vee2014.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1989/CS/CS0578.pdf), p. 1; *SIAM J. Discrete Math*. 3 (1990), no. 3, 330–337. 1. Dirk Hachenberger, *Completely free elements*, in Cohen & Niederreiter (1996) pp. 97–107 Zbl [0864.11066](https://zbmath.org/?q=an:0864.11066) - *Finite Fields and Applications. Proceedings of the 3rd international conference, Glasgow, UK, July 11–14, 1995*. Vol. 233. London Mathematical Society Lecture Note Series. [Cambridge University Press](/source/Cambridge_University_Press). 1996. 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](/source/Mathematics_of_Computation)*. **48** (177): 217–231. [doi:10.2307/2007886](https://doi.org/10.2307/2007886). [hdl:1887/3824](https://hdl.handle.net/1887/3824). [JSTOR 2007886](https://www.jstor.org/stable/2007886). Zbl 0615.12023. - *Applications of finite fields*. Vol. 199. The Kluwer International Series in Engineering and Computer Science. Boston: Kluwer Academic Publishers. 1993. ISBN 978-0792392828. Zbl 0779.11059. --- Adapted from the Wikipedia article [Normal basis](https://en.wikipedia.org/wiki/Normal_basis) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Normal_basis?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.