Normal basis

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 [math]\displaystyle{ F\subset K }[/math] be a Galois extension with Galois group [math]\displaystyle{ G }[/math]. The classical normal basis theorem states that there is an element [math]\displaystyle{ \beta\in K }[/math] such that [math]\displaystyle{ \{g(\beta) \ \textrm{ for }\ g\in G\} }[/math] forms a basis of K, considered as a vector space over F. That is, any element [math]\displaystyle{ \alpha \in K }[/math] can be written uniquely as [math]\displaystyle{ \textstyle\alpha = \sum_{g\in G} a_g\, g(\beta) }[/math] for coefficients [math]\displaystyle{ a_g\in F. }[/math]

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

Case of finite fields

For finite fields this can be stated as follows: Let [math]\displaystyle{ F = GF(q)=\mathbb{F}_q }[/math] denote the field of q elements, where q = p^m is a prime power, and let [math]\displaystyle{ K=GF(q^n)=\mathbb{F}_{q^n} }[/math] denote its extension field of degree n ≥ 1. Here the Galois group is [math]\displaystyle{ G = \text{Gal}(K/F) = \{1,\Phi,\Phi^2,\ldots,\Phi^{n-1}\} }[/math] with [math]\displaystyle{ \Phi^n = 1, }[/math] a cyclic group generated by the relative Frobenius automorphism [math]\displaystyle{ \Phi(\alpha)=\alpha^q, }[/math]with [math]\displaystyle{ \Phi^n = 1 =\textrm{Id}_K. }[/math] Then there exists an element β ∈ K such that

[math]\displaystyle{ \{\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]\displaystyle{ \Phi }[/math] with [math]\displaystyle{ \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]\displaystyle{ \chi(h_1h_2)=\chi(h_1)\chi(h_2) }[/math]; then any distinct characters [math]\displaystyle{ \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]\displaystyle{ \chi_i=\Phi^i: K \to K, }[/math] thought of as mappings from the multiplicative group [math]\displaystyle{ H=K^\times }[/math]. Now [math]\displaystyle{ K\cong F^n }[/math]as an F-vector space, so we may consider [math]\displaystyle{ \Phi : F^n\to F^n }[/math] as an element of the matrix algebra [math]\displaystyle{ M_n(F); }[/math] since its powers [math]\displaystyle{ 1,\Phi,\ldots,\Phi^{n-1} }[/math] are linearly independent (over K and a fortiori over F), its minimal polynomial must have degree at least n, i.e. it must be [math]\displaystyle{ X^n-1 }[/math]. We conclude that the group algebra of G is [math]\displaystyle{ F[G]\cong F[X]/(X^n{-}\,1), }[/math] a quotient of the polynomial ring F[X], and the F-vector space K is a module (or representation) for this algebra.

The second basic fact is the classification of modules over a PID such as F[G]. These are just direct sums of cyclic modules of the form [math]\displaystyle{ F[X]/(f(x)), }[/math] where f(x) must be divisible by Xⁿ − 1. (Here G acts by [math]\displaystyle{ \Phi\cdot X^i = X^{i+1}. }[/math]) But since [math]\displaystyle{ \dim_F F[X]/(X^n{-}\,1) = \dim_F(K) = n, }[/math] we can only have f(x) = Xⁿ − 1, and

[math]\displaystyle{ K \ \cong\ F[X]/(X^n{-}\,1) }[/math]

as F[G]-modules, namely the regular representation of G. (Note this is not an isomorphism of rings or F-algebras!) Now the basis [math]\displaystyle{ \{1,X,X^2,\ldots,X^{n-1}\} }[/math] on the right side of this isomorphism corresponds to a normal basis [math]\displaystyle{ \{\beta, \Phi(\beta),\Phi^2(\beta),\ldots,\Phi^{m-1}(\beta)\} }[/math] of K on the left.

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

Example

Consider the field [math]\displaystyle{ K=GF(2^3)=\mathbb{F}_{8} }[/math] over [math]\displaystyle{ F=GF(2)=\mathbb{F}_{2} }[/math], with Frobenius automorphism [math]\displaystyle{ \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]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ F\subset K }[/math], while the second is isomorphic as an F[G]-module to [math]\displaystyle{ \mathbb{F}_{2^2} \cong \mathbb{F}_2[X]/(X^2{+}X{+}1) }[/math] under the action [math]\displaystyle{ \Phi\cdot X^i = X^{i+1}. }[/math] (Thus [math]\displaystyle{ K \cong \mathbb F_2\oplus \mathbb F_4 }[/math] as F[G]-modules, but not as F-algebras.)

The elements [math]\displaystyle{ \beta\in K }[/math] which can be used for a normal basis are precisely those outside either of the submodules, so that [math]\displaystyle{ (\Phi{+}1)(\beta)\neq 0 }[/math] and [math]\displaystyle{ (\Phi^2{+}\Phi{+}1)(\beta)\neq 0 }[/math]. In terms of the G-orbits of K, which correspond to the irreducible factors of:

[math]\displaystyle{ t^{2^3}-t \ = \ t(t{+}1)(t^3{+}t{+}1)(t^3{+}t^2{+}1)\ \in\ F[t], }[/math]

the elements of [math]\displaystyle{ F=\mathbb{F}_2 }[/math] are the roots of [math]\displaystyle{ t(t{+}1) }[/math], the nonzero elements of the submodule [math]\displaystyle{ \mathbb{F}_4 }[/math] are the roots of [math]\displaystyle{ 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]\displaystyle{ t^3{+}t^2{+}1 }[/math].

By contrast, for the extension field [math]\displaystyle{ L = GF(2^4)=\mathbb{F}_{16} }[/math] in which n = 4 is divisible by p = 2, we have the F[G]-module isomorphism

[math]\displaystyle{ L \ \cong\ \mathbb{F}_2[X]/(X^4{-}1) \ =\ \mathbb{F}_2[X]/(X{+}1)^4. }[/math]

Here the operator [math]\displaystyle{ \Phi\cong X }[/math] is not diagonalizable, the module L has nested submodules given by generalized eigenspaces of [math]\displaystyle{ \Phi }[/math], and the normal basis elements β are those outside the largest proper generalized eigenspace, the elements with [math]\displaystyle{ (\Phi{+}1)^3(\beta)\neq 0 }[/math].

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 [math]\displaystyle{ K=GF(2^3)=\mathbb{F}_{8} }[/math] above, we may represent elements as bit-strings:

[math]\displaystyle{ \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]\displaystyle{ a_i\in GF(2)=\{0,1\}. }[/math] Now we can square elements by doing a left circular shift, [math]\displaystyle{ \alpha^2=\Phi(a_2,a_1,a_0) = (a_1,a_0,a_2) }[/math], since squaring β⁴ gives β⁸ = β. This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring.

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 of E, that is a generator of the multiplicative group [math]\displaystyle{ K^\times. }[/math] (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 K/F is a Galois extension and x in E 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.

See also

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

References

• Cohen, S.; Niederreiter, H., eds (1996). Finite Fields and Applications. Proceedings of the 3rd international conference, Glasgow, UK, July 11–14, 1995. London Mathematical Society Lecture Note Series. 233. Cambridge University Press. ISBN 978-0-521-56736-7. 
• Lenstra, H.W., jr; Schoof, R.J. (1987). "Primitive normal bases for finite fields". Mathematics of Computation 48 (177): 217–231. doi:10.2307/2007886. 
• Menezes, Alfred J., ed (1993). Applications of finite fields. The Kluwer International Series in Engineering and Computer Science. 199. Boston: Kluwer Academic Publishers. ISBN 978-0792392828.