Normal basis

Uses your system voice; voice and rate in settings.

Snapshot

≈ 10 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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\subseteq 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 \{\sigma(\beta) : \sigma\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 \alpha = \sum_{\sigma\in G} a_\sigma\, \sigma(\beta) for some coefficients a_\sigma\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] . 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; thus K is also a left module for the group algebra F[G]. Every homomorphism of left F[G]-modules \phi:F[G]\rightarrow K is of form \phi(\sigma) = \sigma(\beta) for some \beta \in K . Since \{\sigma : \sigma \in G\} is a linear basis of F[G] over F, we see 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 a left F[G] -module: K is isomorphic to the regular representation. Also, a given \beta generates a normal basis iff, when considering K as a G-representation, \beta does not lie in any proper subrepresentation. For finite fields this can be stated as follows: Let F = \mathrm{GF}(q)=\mathbb{F}_q denote the field of q elements, where is a prime power, and let K= \mathrm{GF}(q^n)=\mathbb{F}_{q^n} denote its extension field of degree . 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 generated by the q-power Frobenius automorphism \Phi(\alpha)=\alpha^q, with \Phi^n = 1 =\mathrm{Id}_K. Then there exists an element 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. 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 \chi from a group H to a field K satisfying \chi(h_1h_2)=\chi(h_1)\chi(h_2) and \chi(1)=1 ; then any distinct characters \chi_1,\chi_2,\ldots are linearly independent in the K -vector space of mappings H\to K . 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^n as an F-vector space, so we may consider \Phi : F^n\to F^n as an element of M_n(F)\subset M_n(K) ; since its powers 1,\Phi,\ldots,\Phi^{n-1} are linearly independent over K in M_n(K) and a fortiori over F in M_n(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 modules over a PID such as F[X] . Every such module M of finite dimension over F can be represented as M \cong\bigoplus_{i=1}^k \frac{F[X]}{(f_i(X))} , where f_i(X) are monic polynomials and f_{i+1}(X) is a multiple of f_i(X) , so that the highest f_k(X) is the monic polynomial of smallest degree annihilating the module. For our cyclic Galois group G of order n, we have an F -algebra isomorphism F[G]\cong \frac {F[X]}{(X^n-1)} taking the generator \Phi to the variable X : this makes every F[G] -module into an F[X] -module. Consider M=K as an F[X] -module under X\alpha = \Phi(\alpha) : the minimal monic polynomial f_k(X) annihilating M is the minimal polynomial of \Phi , namely f_k(X)=X^n-1 . Since \dim_F(M) = n, we can only have k=1 , and K \cong \frac{F[X]}{(X^n{-}\,1)} as F[X] -modules (but this is not an isomorphism of rings). Thus we have an isomorphism of F[G] -modules K \cong \frac{F[X]}{(X^n{-}\,1)}\cong F[G] , under which the basis \{1,X,X^2,\ldots,X^{n-1}\} corresponds to the basis \{1,\Phi,\Phi^2,\ldots,\Phi^{n-1}\} of F[G] on the right side, and 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 characteristic zero for a cyclic Kummer extension. 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): 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 rings.) 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 in: 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=\mathbb{F}_2 are the roots of t(t{+}1) ; and 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 is divisible by , 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, 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)\neq 0 . 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, \alpha^2=\Phi(a_2,a_1,a_0) = (a_1,a_0,a_2) , since squaring β 4 gives . This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring. n=[K:F] , G = \text{Gal}(K/F) = \{\sigma_1...\sigma_n\} with \sigma_1 = \text{Id} . By the primitive element theorem there exists \alpha \in K such that K=F[\alpha] and \sigma_i(\alpha)\ne\sigma_j(\alpha) for i\ne j ; and write \alpha_i = \sigma_i(\alpha) . The minimal polynomial f of \alpha over K is: f(X) = \prod_{i=1}^n(X - \alpha_i), a degree n monic polynomial which is irreducible in K[X] . Since f is separable (having simple roots) we may define the Lagrange interpolation polynomials g_1(X), \ldots, g_n(X) satisfying g_i(\alpha_i) = 1 and g_i(\alpha_j) = 0 for i\neq j : \begin {align} g(X) &=\ \frac{f(X)}{(X-\alpha)f'(\alpha)} \ =\ \prod_{\begin {array}{c}1 \le j \le n \\ j\ne 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 \le j \le n \\ j\ne i\end {array}}\frac{X-\alpha_j}{\alpha_i - \alpha_j} . \end {align} Next, define an n \times n matrix of polynomials A = (A_{ij}(X)) by A_{ij}(X) = \sigma_i(\sigma_j(g(X)) = \sigma_i(g_j(X)), and let D(X) = \det A(X) . To see this a non-zero polynomial, observe that A_{ij}(X) = g_k(X) , where k is determined by \sigma_k = \sigma_i \cdot \sigma_j , and k=1 iff \sigma_i = \sigma_j^{-1} ; thus A(\alpha) is the permutation matrix corresponding to the permutation of G which sends each \sigma_i to \sigma_i^{-1} , and D(\alpha) = \det A(\alpha) = \pm 1 . Since 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\in F with D(a)\ne 0 . Define \beta = g(a), \qquad \beta_i = g_i(a) = \sigma_i(\beta). We claim that \{\beta_1, \ldots, \beta_n\} is a normal basis; i.e. that \beta_1, \ldots,\beta_n are linearly independent over F. Suppose \sum_{j=1}^n c_j \beta_j = 0 for some \vec c=(c_1,...,c_n)\in F^n ; applying any \sigma_i gives \sum_{j=1}^n c_j \sigma_i(g_j(a)) = 0 , so that A(a) \cdot \vec{c} = \vec{0} . Since \det A(a) = D(a) \ne 0 , we conclude that \vec{c} = \vec{0} , which completes the proof. It is tempting to take a=\alpha because D(\alpha)\neq0 , but we need a \in F to conclude that \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} .

Text derived from https://en.wikipedia.org/w/index.php?oldid=1369330128 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.