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 $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 )\text{<mrow data-mjx-texclass="ORD">for</mrow>}g\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 _{g\in G}{a}_{g}g(\beta )$ for coefficients $a_g\in F.$

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

Case of finite fields

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

$\{\beta ,\mathrm{\Phi }(\beta ),{\mathrm{\Phi }}^2(\beta ),\dots ,{\mathrm{\Phi }}^{n-1}(\beta )\}=\{\beta ,{\beta }^q,{\beta }^{q^2},\dots ,{\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 $\mathrm{\Phi }$ with ${\mathrm{\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 χ from a group H to a field K satisfying $\chi (h_1{h}_2)=\chi (h_1)\chi (h_2)$; then any distinct characters ${\chi }_1,{\chi }_2,\dots$ are linearly independent in the K-vector space of mappings. We apply this to the Galois group automorphisms ${\chi }_i={\mathrm{\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 $\mathrm{\Phi }:F^n\to F^n$ as an element of the matrix algebra $M_n(F);$ since its powers $1,\mathrm{\Phi },\dots ,{\mathrm{\Phi }}^{n-1}$ are linearly independent (over K and a fortiori over F), its minimal polynomial must have degree at least n, i.e. it must be $X^n-1$. We conclude that the group algebra of G is $F[G]\cong F[X]/(X^n-1),$ 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

$F[X]/(f(x)),$

where f(x) must be divisible by Xⁿ − 1. (Here G acts by

$\mathrm{\Phi }\cdot X^i=X^{i+1}.$

) But since

${\dim }_{F}F[X]/(X^n-1)={\dim }_F(K)=n,$

we can only have f(x) = Xⁿ − 1, and

$K\cong F[X]/(X^n-1)$

as F[G]-modules, namely the regular representation of G. (Note this is not an isomorphism of rings or F-algebras!) Now the basis

$\{1,X,X^2,\dots ,X^{n-1}\}$

on the right side of this isomorphism corresponds to a normal basis

$\{\beta ,\mathrm{\Phi }(\beta ),{\mathrm{\Phi }}^2(\beta ),\dots ,{\mathrm{\Phi }}^{m-1}(\beta )\}$

of K on the left.

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

Example

Consider the field $K=GF(2^3)={\mathbb{𝔽}}_8$ over $F=GF(2)={\mathbb{𝔽}}_2$, with Frobenius automorphism $\mathrm{\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{𝔽}}_{2^2}\cong {\mathbb{𝔽}}_2[X]/(X^2+X+1)$ under the action $\mathrm{\Phi }\cdot X^i=X^{i+1}.$ (Thus $K\cong {\mathbb{𝔽}}_2\oplus {\mathbb{𝔽}}_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 $(\mathrm{\Phi }+1)(\beta )\ne 0$ and $({\mathrm{\Phi }}^2+\mathrm{\Phi }+1)(\beta )\ne 0$. In terms of the G-orbits of K, which correspond to the irreducible factors of:

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

the elements of $F={\mathbb{𝔽}}_2$ are the roots of $t(t+1)$, the nonzero elements of the submodule ${\mathbb{𝔽}}_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=GF(2^4)={\mathbb{𝔽}}_{16}$ in which n = 4 is divisible by p = 2, we have the F[G]-module isomorphism

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

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

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

$K=GF(2^3)={\mathbb{𝔽}}_8$

above, we may represent elements as bit-strings:

$\alpha =(a_2,a_1,a_0)=a_2{\mathrm{\Phi }}^2(\beta )+a_1\mathrm{\Phi }(\beta )+a_0\beta =a_2{\beta }^4+a_1{\beta }^2+a_0\beta ,$

where the coefficients are bits

$a_i\in GF(2)=\{0,1\}.$

Now we can square elements by doing a left circular shift,

${\alpha }^2=\mathrm{\Phi }(a_2,a_1,a_0)=(a_1,a_0,a_2)$

, 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 $K^{\times }.$ (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.