Normal basis theorem
Let
be a Galois extension with Galois group
. The classical normal basis theorem states that there is an element
such that
forms a basis of K, considered as a vector space over F. That is, any element
can be written uniquely as
for some elements
A normal basis contrasts with a primitive element basis of the form
, where
is an element whose minimal polynomial has degree
.
Case of finite fields
For finite fields this can be stated as follows:[1] Let
denote the field of q elements, where q = pm is a prime power, and let
denote its extension field of degree n ≥ 1. Here the Galois group is
with
a cyclic group generated by the q-power Frobenius automorphism
with
Then there exists an element β ∈ K such that
![{\displaystyle \{\beta ,\Phi (\beta ),\Phi ^{2}(\beta ),\ldots ,\Phi ^{n-1}(\beta )\}\ =\ \{\beta ,\beta ^{q},\beta ^{q^{2)),\ldots ,\beta ^{q^{n-1))\!\))](https://wikimedia.org/api/rest_v1/media/math/render/svg/07bdf7ef91f56c9039c162c240ba1a7a031b9d9b)
is a basis of K over F.
Proof for finite fields
In case the Galois group is cyclic as above, generated by
with
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
; then any distinct characters
are linearly independent in the K-vector space of mappings. We apply this to the Galois group automorphisms
thought of as mappings from the multiplicative group
. Now
as an F-vector space, so we may consider
as an element of the matrix algebra Mn(F); since its powers
are linearly independent (over K and a fortiori over F), its minimal polynomial must have degree at least n, i.e. it must be
.
The second basic fact is the classification of finitely generated modules over a PID such as
. Every such module M can be represented as
, where
may be chosen so that they are monic polynomials or zero and
is a multiple of
.
is the monic polynomial of smallest degree annihilating the module, or zero if no such non-zero polynomial exists. In the first case
, in the second case
. In our case of cyclic G of size n generated by
we have an F-algebra isomorphism
where X corresponds to
, so every
-module may be viewed as an
-module with multiplication by X being multiplication by
. In case of K this means
, so the monic polynomial of smallest degree annihilating K is the minimal polynomial of
. Since K is a finite dimensional F-space, the representation above is possible with
. Since
we can only have
, and
as F[X]-modules. (Note this is an isomorphism of F-linear spaces, but not of rings or F-algebras.) This gives isomorphism of
-modules
that we talked about above, and under it the basis
on the right side corresponds to a normal basis
of K on the left.
Note that this proof would also apply in the case of a cyclic Kummer extension.
Example
Consider the field
over
, with Frobenius automorphism
. 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
![{\displaystyle X^{n}-1\ =\ X^{3}-1\ =\ (X{-}1)(X^{2}{+}X{+}1)\ \in \ F[X]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dfce5ffb95d82c40855b1795cabcc39ccd407d63)
means we have a direct sum of F[G]-modules (by the Chinese remainder theorem):![{\displaystyle K\ \cong \ {\frac {F[X]}{(X^{3}{-}\,1)))\ \cong \ {\frac {F[X]}{(X{+}1)))\oplus {\frac {F[X]}{(X^{2}{+}X{+}1))).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/607508c17c6af9570c384a0269482db42df1867f)
The first component is just
, while the second is isomorphic as an F[G]-module to
under the action
(Thus
as F[G]-modules, but not as F-algebras.)
The elements
which can be used for a normal basis are precisely those outside either of the submodules, so that
and
. In terms of the G-orbits of K, which correspond to the irreducible factors of:
![{\displaystyle t^{2^{3))-t\ =\ t(t{+}1)\left(t^{3}+t+1\right)\left(t^{3}+t^{2}+1\right)\ \in \ F[t],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2961e1543a2c38cc88bbd0b2d975a099d2bc354e)
the elements of
are the roots of
, the nonzero elements of the submodule
are the roots of
, while the normal basis, which in this case is unique, is given by the roots of the remaining factor
.
By contrast, for the extension field
in which n = 4 is divisible by p = 2, we have the F[G]-module isomorphism
![{\displaystyle L\ \cong \ \mathbb {F} _{2}[X]/(X^{4}{-}1)\ =\ \mathbb {F} _{2}[X]/(X{+}1)^{4}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4cf98a4e5be183650b61a5d7e301335303dffb65)
Here the operator
is not diagonalizable, the module L has nested submodules given by generalized eigenspaces of
, and the normal basis elements β are those outside the largest proper generalized eigenspace, the elements with
.
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
above, we may represent elements as bit-strings:
![{\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 ,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a3428f0ee66194f774bbcadf285486f4e09673f)
where the coefficients are bits
Now we can square elements by doing a left circular shift,
, since squaring β4 gives β8 = β. This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring.
Proof for the case of infinite fields
Suppose
is a finite Galois extension of the infinite field F. Let [K : F] = n,
, where
. By the primitive element theorem there exists
such
and
. Let us write
.
's (monic) minimal polynomial f over K is the irreducible degree n polynomial given by the formula
![{\displaystyle {\begin{aligned}f(X)&=\prod _{i=1}^{n}(X-\alpha _{i})\end{aligned))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9a5c5b0ff44ddb17eb7cbd6ecb211496fcb1893a)
Since f is separable (it has simple roots) we may define
![{\displaystyle {\begin{aligned}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{aligned))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dbcd683a515741a532c84af1a3fe6f9ce53af5c4)
In other words,
![{\displaystyle {\begin{aligned}g_{i}(X)&=\prod _{\begin{array}{c}1\leq j\leq n\\j\neq i\end{array)){\frac {X-\alpha _{j)){\alpha _{i}-\alpha _{j))}\\g(X)&=g_{1}(X).\end{aligned))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3c3b73f2c32acc335b381feb6b1ebd6019cb8238)
Note that
and
for
. Next, define an
matrix A of polynomials over K and a polynomial D by
![{\displaystyle {\begin{aligned}A_{ij}(X)&=\sigma _{i}(\sigma _{j}(g(X))=\sigma _{i}(g_{j}(X))\\D(X)&=\det A(X).\end{aligned))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fa7965ba532f3fb78ed93f83ce90037929b63ee)
Observe that
, where k is determined by
; in particular
iff
. It follows that
is the permutation matrix corresponding to the permutation of G which sends each
to
. (We denote by
the matrix obtained by evaluating
at
.) Therefore,
. 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
such that
. Define
![{\displaystyle {\begin{aligned}\beta &=g(a)\\\beta _{i}&=g_{i}(a)=\sigma _{i}(\beta ).\end{aligned))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2715bee146961fc04db4c9067eb1afa0f20abd8c)
We claim that
is a normal basis. We only have to show that
are linearly independent over F, so suppose
for some
. Applying the automorphism
yields
for all i. In other words,
. Since
, we conclude that
, which completes the proof.
It is tempting to take
because
. But this is impermissible because we used the fact that
to conclude that for any F-automorphism
and polynomial
over
the value of the polynomial
at a equals
.
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×. (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 K 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 KH, x is free for K / KH, then x is said to be completely free in K / F. Every Galois extension has a completely free element.[2]