{
  "id": "enwiki-001369330128",
  "slug": "normal-basis",
  "title": "Normal basis",
  "qid": "",
  "lead": "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.",
  "body": "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} .",
  "categories": [
    "20178173",
    "20353103",
    "23060232",
    "23603337",
    "26220375",
    "39997765"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1369330128",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1786690536.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001369330128",
    "type": "webpage",
    "title": "Normal basis",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/normal-basis",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001369330128",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1369330128",
    "note": "Immutable snapshot enwiki-001369330128"
  }
}