Editing Normal basis

In [[mathematics]], specifically the [[Abstract algebra|algebraic]] theory of [[field theory (mathematics)|fields]], a '''normal basis''' is a special kind of [[basis (linear algebra)|basis]] for [[Galois extension]]s of finite degree, characterised as forming a single [[orbit (group theory)|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 <math>F\subset K</math> be a Galois extension with Galois group <math>G</math>. The classical '''normal basis theorem''' states that there is an element <math>\beta\in K</math> such that <math>\{g(\beta) : g\in G\}</math> forms a basis of ''K'', considered as a vector space over ''F''. That is, any element <math>\alpha \in K</math> can be written uniquely as <math display="inline">\alpha = \sum_{g\in G} a_g\, g(\beta)</math> for some elements <math>a_g\in F.</math>

A normal basis contrasts with a [[Primitive element theorem|primitive element]] basis of the form <math>\{1,\beta,\beta^2,\ldots,\beta^{n-1}\}</math>, where <math>\beta\in K</math> is an element whose minimal polynomial has degree <math>n=[K:F]</math>.

== Group representation point of view ==
A field extension {{nowrap|''K'' / ''F''}} with Galois group ''G'' can be naturally viewed as a [[Group representation|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 ring|group algebra]] ''F''[''G'']. Every homomorphism of left ''F''[''G'']-modules <math>\phi:F[G]\rightarrow K</math> is of form <math>\phi(r) = r\beta</math> for some <math>\beta \in K</math>. Since <math>\{1\cdot \sigma| \sigma \in G\}</math> is a linear basis of ''F''[''G''] over ''F'', it follows easily that <math>\phi</math> is bijective iff <math>\beta</math> generates a normal basis of ''K'' over ''F''. The normal basis theorem therefore amounts to the statement saying  that if {{nowrap|''K'' / ''F''}} is finite Galois extension, then <math>K \cong F[G]</math> as a left <math>F[G]</math>-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 field]]s this can be stated as follows:<ref>{{citation|author1=Nader H. Bshouty|title=Generalizations of the normal basis theorem of finite fields|url=https://hotcrp-vee2014.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1989/CS/CS0578.pdf|page=1|year=1989|author2=Gadiel Seroussi}}; ''SIAM J. Discrete Math''. 3 (1990), no. 3, 330–337.</ref> Let <math>F = \mathrm{GF}(q)=\mathbb{F}_q</math> denote the field of ''q'' elements, where {{nowrap|1=''q'' = ''p''<sup>''m''</sup>}} is a prime power, and let <math>K= \mathrm{GF}(q^n)=\mathbb{F}_{q^n}</math> denote its extension field of degree {{nowrap|''n'' ≥ 1}}.  Here the Galois group is <math>G = \text{Gal}(K/F) = \{1,\Phi,\Phi^2,\ldots,\Phi^{n-1}\}</math> with <math>\Phi^n = 1,</math> a [[cyclic group]] generated by the ''q''-power [[Frobenius endomorphism|Frobenius automorphism]] <math>\Phi(\alpha)=\alpha^q,</math>with <math>\Phi^n = 1 =\mathrm{Id}_K.</math> Then there exists an element {{nowrap|''β'' ∈ ''K''}} such that
<math display="block">\{\beta, \Phi(\beta), \Phi^2(\beta),\ldots,\Phi^{n-1}(\beta)\}
\ = \ 
\{\beta, \beta^q, \beta^{q^2}, \ldots,\beta^{q^{n-1}}\!\}</math>
is a basis of ''K'' over ''F''.

=== Proof for finite fields ===
In case the Galois group is cyclic as above, generated by <math>\Phi</math> with <math>\Phi^n=1,</math> 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 <math>\chi(h_1h_2)=\chi(h_1)\chi(h_2)</math>; then any distinct characters <math>\chi_1,\chi_2,\ldots </math> are linearly independent in the ''K''-vector space of mappings. We apply this to the Galois group automorphisms <math>\chi_i=\Phi^i: K \to K,</math> thought of as mappings from the multiplicative group <math>H=K^\times</math>. Now  <math>K\cong F^n</math>as an ''F''-vector space, so we may consider <math>\Phi : F^n\to F^n</math> as an element of the matrix algebra M<sub>''n''</sub>(''F''); since its powers <math>1,\Phi,\ldots,\Phi^{n-1}</math> are linearly independent (over ''K'' and a fortiori over ''F''), its [[minimal polynomial (field theory)|minimal polynomial]] must have degree at least ''n'', i.e. it must be <math>X^n-1</math>.

The second basic fact is the classification of finitely generated [[Modules over a pid|modules over a PID]] such as <math>F[X]</math>. Every such module ''M'' can be represented as <math display="inline">M \cong\bigoplus_{i=1}^k \frac{F[X]}{(f_i(X))}</math>, where <math>f_i(X)</math> may be chosen so that they are monic polynomials or zero and <math>f_{i+1}(X)</math> is a multiple of <math>f_i(X)</math>. <math>f_k(X)</math> is the monic polynomial of smallest degree annihilating the module, or zero if no such non-zero polynomial exists. In the first case <math display="inline">\dim_F M = \sum_{i=1}^k \deg f_i</math>, in the second case <math>\dim_F M = \infty</math>. In our case of cyclic ''G'' of size ''n'' generated by <math>\Phi</math> we have an ''F''-algebra isomorphism <math display="inline">F[G]\cong \frac {F[X]}{(X^n-1)}</math> where ''X'' corresponds to <math>1 \cdot \Phi</math>, so every <math>F[G]</math>-module may be viewed as an <math>F[X]</math>-module with multiplication by ''X'' being multiplication by <math>1\cdot\Phi</math>. In case of ''K'' this means <math>X\alpha = \Phi(\alpha)</math>, so the monic polynomial of smallest degree annihilating ''K'' is the minimal polynomial of <math>\Phi</math>. Since ''K'' is a finite dimensional ''F''-space, the representation above is possible with <math>f_k(X)=X^n-1</math>. Since <math>\dim_F(K) = n,</math> we can only have <math>k=1</math>, and <math display="inline">K \cong \frac{F[X]}{(X^n{-}\,1)}</math> as ''F''[''X'']-modules. (Note this is  an isomorphism of ''F''-linear spaces, but ''not'' of rings or ''F''-algebras.) This gives isomorphism of <math>F[G]</math>-modules <math>K\cong F[G]</math> that we talked about above, and under it the basis <math>\{1,X,X^2,\ldots,X^{n-1}\}</math> on the right side corresponds to a normal basis <math>\{\beta, \Phi(\beta),\Phi^2(\beta),\ldots,\Phi^{n-1}(\beta)\}</math> of ''K'' on the left.

Note that this proof would also apply in the case of a cyclic [[Kummer theory|Kummer extension]].

=== Example ===
Consider the field <math>K=\mathrm{GF}(2^3)=\mathbb{F}_{8}</math> over <math>F=\mathrm{GF}(2)=\mathbb{F}_{2}</math>, with Frobenius automorphism <math>\Phi(\alpha)=\alpha^2</math>. 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 
<math display=block>X^n-1 \ =\ X^3-1\ = \ (X{-}1)(X^2{+}X{+}1) \ \in\ F[X]</math> means we have a direct sum of ''F''[''G'']-modules (by the [[Chinese remainder theorem]]):<math display=block>K\ \cong\ \frac{F[X]}{(X^3{-}\,1)} \ \cong\ \frac{F[X]}{(X{+}1)} \oplus \frac{F[X]}{(X^2{+}X{+}1)}.</math>
The first component is just <math>F\subset K</math>, while the second is isomorphic as an ''F''[''G'']-module to <math>\mathbb{F}_{2^2} \cong \mathbb{F}_2[X]/(X^2{+}X{+}1)</math> under the action <math>\Phi\cdot X^i = X^{i+1}.</math> (Thus <math>K \cong \mathbb F_2\oplus \mathbb F_4</math> as ''F''[''G'']-modules, but ''not'' as ''F''-algebras.)

The elements <math>\beta\in K</math> which can be used for a normal basis are precisely those outside either of the submodules, so that <math>(\Phi{+}1)(\beta)\neq 0</math> and <math>(\Phi^2{+}\Phi{+}1)(\beta)\neq 0</math>. In terms of the ''G''-orbits of ''K'', which correspond to the irreducible factors of:
<math display="block">t^{2^3}-t \ = \ t(t{+}1)\left(t^3 + t + 1\right)\left(t^3 + t^2 + 1\right)\ \in\ F[t],</math>
the elements of <math>F=\mathbb{F}_2</math> are the roots of <math>t(t{+}1)</math>, the nonzero elements of the submodule <math>\mathbb{F}_4</math> are the roots of <math>t^3+t+1</math>, while the normal basis, which in this case is unique, is given by the roots of the remaining factor <math>t^3{+}t^2{+}1</math>.

By contrast, for the extension field <math>L = \mathrm{GF}(2^4)=\mathbb{F}_{16}</math> in which {{nowrap|1=''n'' = 4}} is divisible by {{nowrap|1=''p'' = 2}}, we have the ''F''[''G'']-module isomorphism 
<math display="block">L \ \cong\ \mathbb{F}_2[X]/(X^4{-}1)\ =\ \mathbb{F}_2[X]/(X{+}1)^4.</math>
Here the operator <math>\Phi\cong X</math> is not [[Diagonalizable matrix|diagonalizable]], the module ''L'' has nested submodules given by [[Generalized eigenvector|generalized eigenspaces]] of <math>\Phi</math>, and the normal basis elements ''β'' are those outside the largest proper generalized eigenspace, the elements with <math>(\Phi{+}1)^3(\beta)\neq 0</math>.

=== Application to cryptography ===
The normal basis is frequently used in [[cryptography|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 <math>K=\mathrm{GF}(2^3)=\mathbb{F}_{8}</math> above, we may represent elements as bit-strings:
<math display="block">\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,</math>
where the coefficients are bits <math>a_i\in \mathrm{GF}(2)=\{0,1\}.</math> Now we can square elements by doing a left circular shift, <math>\alpha^2=\Phi(a_2,a_1,a_0) = (a_1,a_0,a_2)</math>, since squaring ''β''<sup>4</sup> gives {{nowrap|1=''β''<sup>8</sup> = ''β''}}.  This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring.

== Proof for the case of infinite fields ==
Suppose <math>K/F</math> is a finite Galois extension of the infinite field ''F''. Let {{nowrap|1=[''K'' : ''F''] = ''n''}}, <math>\text{Gal}(K/F) = G =\{\sigma_1...\sigma_n\}</math>, where <math>\sigma_1 = \text{Id}</math>. By the [[primitive element theorem]] there exists <math>\alpha \in K</math> such <math>i\ne j\implies \sigma_i(\alpha)\ne\sigma_j(\alpha)</math> and <math>K=F[\alpha]</math>. Let us write <math>\alpha_i = \sigma_i(\alpha)</math>. <math>\alpha</math>'s (monic) minimal polynomial ''f'' over ''K'' is the irreducible degree ''n'' polynomial given by the formula
<math display="block">\begin {align}
f(X) &= \prod_{i=1}^n(X - \alpha_i)
\end {align}</math>
Since ''f'' is separable (it has simple roots) we may define 
<math display="block">
\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}
</math>
In other words,
<math display="block">\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}</math>
Note that <math>g(\alpha)=1</math> and <math>g_i(\alpha)=0</math> for <math>i \ne 1</math>. Next, define an <math>n \times n</math> matrix ''A'' of polynomials over ''K'' and a polynomial ''D'' by
<math display="block">
\begin {align}
A_{ij}(X) &= \sigma_i(\sigma_j(g(X)) = \sigma_i(g_j(X))\\
D(X) &= \det A(X).
\end {align}</math>
Observe that <math>A_{ij}(X) = g_k(X)</math>, where ''k'' is determined by <math>\sigma_k = \sigma_i \cdot \sigma_j</math>; in particular <math>k=1</math> iff <math>\sigma_i = \sigma_j^{-1}</math>. It follows that <math>A(\alpha)</math> is the permutation matrix corresponding to the permutation of ''G'' which sends each <math>\sigma_i</math> to <math>\sigma_i^{-1}</math>. (We denote by <math>A(\alpha)</math> the matrix obtained by evaluating <math>A(X)</math> at <math>x=\alpha</math>.) Therefore, <math>D(\alpha) = \det A(\alpha) = \pm 1</math>. 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 <math>a\in F</math> such that <math>D(a)\ne 0</math>. Define
<math display="block">
\begin {align}
\beta &=  g(a) \\ 
\beta_i &= g_i(a) = \sigma_i(\beta).
\end {align}
</math>
We claim that <math>\{\beta_1, \ldots, \beta_n\}</math> is a normal basis. We only have to show that <math>\beta_1, \ldots,\beta_n</math> are linearly independent over ''F'', so suppose <math display="inline">\sum_{j=1}^n x_j \beta_j = 0</math> for some <math>x_1...x_n\in F</math>. Applying the automorphism <math>\sigma_i</math> yields <math display="inline">\sum_{j=1}^n x_j \sigma_i(g_j(a)) = 0</math> for all ''i''. In other words, <math>A(a) \cdot \overline {x} = \overline {0}</math>. Since <math>\det A(a) = D(a) \ne 0</math>, we conclude that <math>\overline x = \overline 0</math>, which completes the proof.

It is tempting to take <math>a=\alpha</math> because <math>D(\alpha)\neq0</math>. But this is impermissible because we used the fact that <math>a \in F</math> to conclude that for any ''F''-automorphism <math>\sigma</math> and polynomial <math>h(X)</math> over <math>K</math> the value of the polynomial <math>\sigma(h(X))</math> at ''a'' equals <math>\sigma(h(a))</math>.

== Primitive normal basis ==
A '''primitive normal basis''' of an extension of finite fields {{nowrap|''E'' / ''F''}} is a normal basis for {{nowrap|''E'' / ''F''}} that is generated by a [[Primitive element (finite field)|primitive element]] of ''E'', that is a generator of the multiplicative group ''K''<sup>×</sup>. (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]].

== Free elements ==
If {{nowrap|''K'' / ''F''}} is a Galois extension and ''x'' in ''K'' generates a normal basis over ''F'', then ''x'' is '''free''' in {{nowrap|''K'' / ''F''}}.  If ''x'' has the property that for every subgroup ''H'' of the Galois  group ''G'', with fixed field ''K''<sup>''H''</sup>, ''x'' is free for {{nowrap|''K'' / ''K''<sup>''H''</sup>}}, then ''x'' is said to be '''completely free''' in {{nowrap|''K'' / ''F''}}.  Every Galois extension has a completely free element.<ref>Dirk Hachenberger, ''Completely free elements'', in Cohen & Niederreiter (1996) pp.&nbsp;97–107 {{zbl|0864.11066}}</ref>

== See also ==
* [[Dual basis in a field extension]]
* [[Polynomial basis]]
* [[Zech's logarithm]]

== References ==
{{Reflist}}
* {{cite book | editor1-first=S. | editor1-last=Cohen | editor2-first=H. | editor2-last=Niederreiter|editor2-link = Harald Niederreiter | title=Finite Fields and Applications. Proceedings of the 3rd international conference, Glasgow, UK, July 11–14, 1995 | publisher=[[Cambridge University Press]] | isbn=978-0-521-56736-7 | year=1996 | series=London Mathematical Society Lecture Note Series | volume=233 | zbl=0851.00052 }}
* {{cite journal | last1=Lenstra | first1=H.W. Jr | author1-link=Hendrik Lenstra | last2=Schoof | first2=R.J. | author2-link=René Schoof | title=Primitive normal bases for finite fields | zbl=0615.12023 | journal=[[Mathematics of Computation]] | volume=48 | issue=177 | pages=217–231 | year=1987 | jstor=2007886 | doi=10.2307/2007886| doi-access=free | hdl=1887/3824 | hdl-access=free }}
* {{cite book | editor1-last=Menezes | editor1-first=Alfred J. | editor1-link=Alfred Menezes | title=Applications of finite fields | zbl=0779.11059 | series=The Kluwer International Series in Engineering and Computer Science | volume=199 | location=Boston | publisher= Kluwer Academic Publishers | year=1993 | isbn=978-0792392828 }}

{{Authority control}}

[[Category:Linear algebra]]
[[Category:Field (mathematics)]]
[[Category:Abstract algebra]]
[[Category:Cryptography]]