- Source: 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
⊂
K
{\displaystyle F\subset K}
be a Galois extension with Galois group
G
{\displaystyle G}
. The classical normal basis theorem states that there is an element
β
∈
K
{\displaystyle \beta \in K}
such that
{
g
(
β
)
:
g
∈
G
}
{\displaystyle \{g(\beta ):g\in G\}}
forms a basis of K, considered as a vector space over F. That is, any element
α
∈
K
{\displaystyle \alpha \in K}
can be written uniquely as
α
=
∑
g
∈
G
a
g
g
(
β
)
{\textstyle \alpha =\sum _{g\in G}a_{g}\,g(\beta )}
for some elements
a
g
∈
F
.
{\displaystyle a_{g}\in F.}
A normal basis contrasts with a primitive element basis of the form
{
1
,
β
,
β
2
,
…
,
β
n
−
1
}
{\displaystyle \{1,\beta ,\beta ^{2},\ldots ,\beta ^{n-1}\}}
, where
β
∈
K
{\displaystyle \beta \in K}
is an element whose minimal polynomial has degree
n
=
[
K
:
F
]
{\displaystyle n=[K:F]}
.
Group representation point of view
A field extension K / F 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. Representations of G over the field F can be viewed as left modules for the group algebra F[G]. Every homomorphism of left F[G]-modules
ϕ
:
F
[
G
]
→
K
{\displaystyle \phi :F[G]\rightarrow K}
is of form
ϕ
(
r
)
=
r
β
{\displaystyle \phi (r)=r\beta }
for some
β
∈
K
{\displaystyle \beta \in K}
. Since
{
1
⋅
σ
|
σ
∈
G
}
{\displaystyle \{1\cdot \sigma |\sigma \in G\}}
is a linear basis of F[G] over F, it follows easily that
ϕ
{\displaystyle \phi }
is bijective iff
β
{\displaystyle \beta }
generates a normal basis of K over F. The normal basis theorem therefore amounts to the statement saying that if K / F is finite Galois extension, then
K
≅
F
[
G
]
{\displaystyle K\cong F[G]}
as left
F
[
G
]
{\displaystyle F[G]}
-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 fields this can be stated as follows: Let
F
=
G
F
(
q
)
=
F
q
{\displaystyle F=\mathrm {GF} (q)=\mathbb {F} _{q}}
denote the field of q elements, where q = pm is a prime power, and let
K
=
G
F
(
q
n
)
=
F
q
n
{\displaystyle K=\mathrm {GF} (q^{n})=\mathbb {F} _{q^{n}}}
denote its extension field of degree n ≥ 1. Here the Galois group is
G
=
Gal
(
K
/
F
)
=
{
1
,
Φ
,
Φ
2
,
…
,
Φ
n
−
1
}
{\displaystyle G={\text{Gal}}(K/F)=\{1,\Phi ,\Phi ^{2},\ldots ,\Phi ^{n-1}\}}
with
Φ
n
=
1
,
{\displaystyle \Phi ^{n}=1,}
a cyclic group generated by the q-power Frobenius automorphism
Φ
(
α
)
=
α
q
,
{\displaystyle \Phi (\alpha )=\alpha ^{q},}
with
Φ
n
=
1
=
I
d
K
.
{\displaystyle \Phi ^{n}=1=\mathrm {Id} _{K}.}
Then there exists an element β ∈ K such that
{
β
,
Φ
(
β
)
,
Φ
2
(
β
)
,
…
,
Φ
n
−
1
(
β
)
}
=
{
β
,
β
q
,
β
q
2
,
…
,
β
q
n
−
1
}
{\displaystyle \{\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.
= Proof for finite fields
=In case the Galois group is cyclic as above, generated by
Φ
{\displaystyle \Phi }
with
Φ
n
=
1
,
{\displaystyle \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
χ
(
h
1
h
2
)
=
χ
(
h
1
)
χ
(
h
2
)
{\displaystyle \chi (h_{1}h_{2})=\chi (h_{1})\chi (h_{2})}
; then any distinct characters
χ
1
,
χ
2
,
…
{\displaystyle \chi _{1},\chi _{2},\ldots }
are linearly independent in the K-vector space of mappings. We apply this to the Galois group automorphisms
χ
i
=
Φ
i
:
K
→
K
,
{\displaystyle \chi _{i}=\Phi ^{i}:K\to K,}
thought of as mappings from the multiplicative group
H
=
K
×
{\displaystyle H=K^{\times }}
. Now
K
≅
F
n
{\displaystyle K\cong F^{n}}
as an F-vector space, so we may consider
Φ
:
F
n
→
F
n
{\displaystyle \Phi :F^{n}\to F^{n}}
as an element of the matrix algebra Mn(F); since its powers
1
,
Φ
,
…
,
Φ
n
−
1
{\displaystyle 1,\Phi ,\ldots ,\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
{\displaystyle X^{n}-1}
.
The second basic fact is the classification of finitely generated modules over a PID such as
F
[
X
]
{\displaystyle F[X]}
. Every such module M can be represented as
M
≅
⨁
i
=
1
k
F
[
X
]
(
f
i
(
X
)
)
{\textstyle M\cong \bigoplus _{i=1}^{k}{\frac {F[X]}{(f_{i}(X))}}}
, where
f
i
(
X
)
{\displaystyle f_{i}(X)}
may be chosen so that they are monic polynomials or zero and
f
i
+
1
(
X
)
{\displaystyle f_{i+1}(X)}
is a multiple of
f
i
(
X
)
{\displaystyle f_{i}(X)}
.
f
k
(
X
)
{\displaystyle f_{k}(X)}
is the monic polynomial of smallest degree annihilating the module, or zero if no such non-zero polynomial exists. In the first case
dim
F
M
=
∑
i
=
1
k
deg
f
i
{\textstyle \dim _{F}M=\sum _{i=1}^{k}\deg f_{i}}
, in the second case
dim
F
M
=
∞
{\displaystyle \dim _{F}M=\infty }
. In our case of cyclic G of size n generated by
Φ
{\displaystyle \Phi }
we have an F-algebra isomorphism
F
[
G
]
≅
F
[
X
]
(
X
n
−
1
)
{\textstyle F[G]\cong {\frac {F[X]}{(X^{n}-1)}}}
where X corresponds to
1
⋅
Φ
{\displaystyle 1\cdot \Phi }
, so every
F
[
G
]
{\displaystyle F[G]}
-module may be viewed as an
F
[
X
]
{\displaystyle F[X]}
-module with multiplication by X being multiplication by
1
⋅
Φ
{\displaystyle 1\cdot \Phi }
. In case of K this means
X
α
=
Φ
(
α
)
{\displaystyle X\alpha =\Phi (\alpha )}
, so the monic polynomial of smallest degree annihilating K is the minimal polynomial of
Φ
{\displaystyle \Phi }
. Since K is a finite dimensional F-space, the representation above is possible with
f
k
(
X
)
=
X
n
−
1
{\displaystyle f_{k}(X)=X^{n}-1}
. Since
dim
F
(
K
)
=
n
,
{\displaystyle \dim _{F}(K)=n,}
we can only have
k
=
1
{\displaystyle k=1}
, and
K
≅
F
[
X
]
(
X
n
−
1
)
{\textstyle K\cong {\frac {F[X]}{(X^{n}{-}\,1)}}}
as F[X]-modules. (Note this is an isomorphism of F-linear spaces, but not of rings or F-algebras.) This gives isomorphism of
F
[
G
]
{\displaystyle F[G]}
-modules
K
≅
F
[
G
]
{\displaystyle K\cong F[G]}
that we talked about above, and under it the basis
{
1
,
X
,
X
2
,
…
,
X
n
−
1
}
{\displaystyle \{1,X,X^{2},\ldots ,X^{n-1}\}}
on the right side corresponds to a normal basis
{
β
,
Φ
(
β
)
,
Φ
2
(
β
)
,
…
,
Φ
n
−
1
(
β
)
}
{\displaystyle \{\beta ,\Phi (\beta ),\Phi ^{2}(\beta ),\ldots ,\Phi ^{n-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
=
G
F
(
2
3
)
=
F
8
{\displaystyle K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}}
over
F
=
G
F
(
2
)
=
F
2
{\displaystyle F=\mathrm {GF} (2)=\mathbb {F} _{2}}
, with Frobenius automorphism
Φ
(
α
)
=
α
2
{\displaystyle \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
)
∈
F
[
X
]
{\displaystyle 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
≅
F
[
X
]
(
X
3
−
1
)
≅
F
[
X
]
(
X
+
1
)
⊕
F
[
X
]
(
X
2
+
X
+
1
)
.
{\displaystyle 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
⊂
K
{\displaystyle F\subset K}
, while the second is isomorphic as an F[G]-module to
F
2
2
≅
F
2
[
X
]
/
(
X
2
+
X
+
1
)
{\displaystyle \mathbb {F} _{2^{2}}\cong \mathbb {F} _{2}[X]/(X^{2}{+}X{+}1)}
under the action
Φ
⋅
X
i
=
X
i
+
1
.
{\displaystyle \Phi \cdot X^{i}=X^{i+1}.}
(Thus
K
≅
F
2
⊕
F
4
{\displaystyle K\cong \mathbb {F} _{2}\oplus \mathbb {F} _{4}}
as F[G]-modules, but not as F-algebras.)
The elements
β
∈
K
{\displaystyle \beta \in K}
which can be used for a normal basis are precisely those outside either of the submodules, so that
(
Φ
+
1
)
(
β
)
≠
0
{\displaystyle (\Phi {+}1)(\beta )\neq 0}
and
(
Φ
2
+
Φ
+
1
)
(
β
)
≠
0
{\displaystyle (\Phi ^{2}{+}\Phi {+}1)(\beta )\neq 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
)
∈
F
[
t
]
,
{\displaystyle t^{2^{3}}-t\ =\ t(t{+}1)\left(t^{3}+t+1\right)\left(t^{3}+t^{2}+1\right)\ \in \ F[t],}
the elements of
F
=
F
2
{\displaystyle F=\mathbb {F} _{2}}
are the roots of
t
(
t
+
1
)
{\displaystyle t(t{+}1)}
, the nonzero elements of the submodule
F
4
{\displaystyle \mathbb {F} _{4}}
are the roots of
t
3
+
t
+
1
{\displaystyle 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
{\displaystyle t^{3}{+}t^{2}{+}1}
.
By contrast, for the extension field
L
=
G
F
(
2
4
)
=
F
16
{\displaystyle L=\mathrm {GF} (2^{4})=\mathbb {F} _{16}}
in which n = 4 is divisible by p = 2, we have the F[G]-module isomorphism
L
≅
F
2
[
X
]
/
(
X
4
−
1
)
=
F
2
[
X
]
/
(
X
+
1
)
4
.
{\displaystyle L\ \cong \ \mathbb {F} _{2}[X]/(X^{4}{-}1)\ =\ \mathbb {F} _{2}[X]/(X{+}1)^{4}.}
Here the operator
Φ
≅
X
{\displaystyle \Phi \cong X}
is not diagonalizable, the module L has nested submodules given by generalized eigenspaces of
Φ
{\displaystyle \Phi }
, and the normal basis elements β are those outside the largest proper generalized eigenspace, the elements with
(
Φ
+
1
)
3
(
β
)
≠
0
{\displaystyle (\Phi {+}1)^{3}(\beta )\neq 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
=
G
F
(
2
3
)
=
F
8
{\displaystyle K=\mathrm {GF} (2^{3})=\mathbb {F} _{8}}
above, we may represent elements as bit-strings:
α
=
(
a
2
,
a
1
,
a
0
)
=
a
2
Φ
2
(
β
)
+
a
1
Φ
(
β
)
+
a
0
β
=
a
2
β
4
+
a
1
β
2
+
a
0
β
,
{\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 ,}
where the coefficients are bits
a
i
∈
G
F
(
2
)
=
{
0
,
1
}
.
{\displaystyle a_{i}\in \mathrm {GF} (2)=\{0,1\}.}
Now we can square elements by doing a left circular shift,
α
2
=
Φ
(
a
2
,
a
1
,
a
0
)
=
(
a
1
,
a
0
,
a
2
)
{\displaystyle \alpha ^{2}=\Phi (a_{2},a_{1},a_{0})=(a_{1},a_{0},a_{2})}
, 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
K
/
F
{\displaystyle K/F}
is a finite Galois extension of the infinite field F. Let [K : F] = n,
Gal
(
K
/
F
)
=
G
=
{
σ
1
.
.
.
σ
n
}
{\displaystyle {\text{Gal}}(K/F)=G=\{\sigma _{1}...\sigma _{n}\}}
, where
σ
1
=
Id
{\displaystyle \sigma _{1}={\text{Id}}}
. By the primitive element theorem there exists
α
∈
K
{\displaystyle \alpha \in K}
such
i
≠
j
⟹
σ
i
(
α
)
≠
σ
j
(
α
)
{\displaystyle i\neq j\implies \sigma _{i}(\alpha )\neq \sigma _{j}(\alpha )}
and
K
=
F
[
α
]
{\displaystyle K=F[\alpha ]}
. Let us write
α
i
=
σ
i
(
α
)
{\displaystyle \alpha _{i}=\sigma _{i}(\alpha )}
.
α
{\displaystyle \alpha }
's (monic) minimal polynomial f over K is the irreducible degree n polynomial given by the formula
f
(
X
)
=
∏
i
=
1
n
(
X
−
α
i
)
{\displaystyle {\begin{aligned}f(X)&=\prod _{i=1}^{n}(X-\alpha _{i})\end{aligned}}}
Since f is separable (it has simple roots) we may define
g
(
X
)
=
f
(
X
)
(
X
−
α
)
f
′
(
α
)
g
i
(
X
)
=
f
(
X
)
(
X
−
α
i
)
f
′
(
α
i
)
=
σ
i
(
g
(
X
)
)
.
{\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}}}
In other words,
g
i
(
X
)
=
∏
1
≤
j
≤
n
j
≠
i
X
−
α
j
α
i
−
α
j
g
(
X
)
=
g
1
(
X
)
.
{\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}}}
Note that
g
(
α
)
=
1
{\displaystyle g(\alpha )=1}
and
g
i
(
α
)
=
0
{\displaystyle g_{i}(\alpha )=0}
for
i
≠
1
{\displaystyle i\neq 1}
. Next, define an
n
×
n
{\displaystyle n\times n}
matrix A of polynomials over K and a polynomial D by
A
i
j
(
X
)
=
σ
i
(
σ
j
(
g
(
X
)
)
=
σ
i
(
g
j
(
X
)
)
D
(
X
)
=
det
A
(
X
)
.
{\displaystyle {\begin{aligned}A_{ij}(X)&=\sigma _{i}(\sigma _{j}(g(X))=\sigma _{i}(g_{j}(X))\\D(X)&=\det A(X).\end{aligned}}}
Observe that
A
i
j
(
X
)
=
g
k
(
X
)
{\displaystyle A_{ij}(X)=g_{k}(X)}
, where k is determined by
σ
k
=
σ
i
⋅
σ
j
{\displaystyle \sigma _{k}=\sigma _{i}\cdot \sigma _{j}}
; in particular
k
=
1
{\displaystyle k=1}
iff
σ
i
=
σ
j
−
1
{\displaystyle \sigma _{i}=\sigma _{j}^{-1}}
. It follows that
A
(
α
)
{\displaystyle A(\alpha )}
is the permutation matrix corresponding to the permutation of G which sends each
σ
i
{\displaystyle \sigma _{i}}
to
σ
i
−
1
{\displaystyle \sigma _{i}^{-1}}
. (We denote by
A
(
α
)
{\displaystyle A(\alpha )}
the matrix obtained by evaluating
A
(
X
)
{\displaystyle A(X)}
at
x
=
α
{\displaystyle x=\alpha }
.) Therefore,
D
(
α
)
=
det
A
(
α
)
=
±
1
{\displaystyle D(\alpha )=\det A(\alpha )=\pm 1}
. 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
a
∈
F
{\displaystyle a\in F}
such that
D
(
a
)
≠
0
{\displaystyle D(a)\neq 0}
. Define
β
=
g
(
a
)
β
i
=
g
i
(
a
)
=
σ
i
(
β
)
.
{\displaystyle {\begin{aligned}\beta &=g(a)\\\beta _{i}&=g_{i}(a)=\sigma _{i}(\beta ).\end{aligned}}}
We claim that
{
β
1
,
…
,
β
n
}
{\displaystyle \{\beta _{1},\ldots ,\beta _{n}\}}
is a normal basis. We only have to show that
β
1
,
…
,
β
n
{\displaystyle \beta _{1},\ldots ,\beta _{n}}
are linearly independent over F, so suppose
∑
j
=
1
n
x
j
β
j
=
0
{\textstyle \sum _{j=1}^{n}x_{j}\beta _{j}=0}
for some
x
1
.
.
.
x
n
∈
F
{\displaystyle x_{1}...x_{n}\in F}
. Applying the automorphism
σ
i
{\displaystyle \sigma _{i}}
yields
∑
j
=
1
n
x
j
σ
i
(
g
j
(
a
)
)
=
0
{\textstyle \sum _{j=1}^{n}x_{j}\sigma _{i}(g_{j}(a))=0}
for all i. In other words,
A
(
a
)
⋅
x
¯
=
0
¯
{\displaystyle A(a)\cdot {\overline {x}}={\overline {0}}}
. Since
det
A
(
a
)
=
D
(
a
)
≠
0
{\displaystyle \det A(a)=D(a)\neq 0}
, we conclude that
x
¯
=
0
¯
{\displaystyle {\overline {x}}={\overline {0}}}
, which completes the proof.
It is tempting to take
a
=
α
{\displaystyle a=\alpha }
because
D
(
α
)
≠
0
{\displaystyle D(\alpha )\neq 0}
. But this is impermissible because we used the fact that
a
∈
F
{\displaystyle a\in F}
to conclude that for any F-automorphism
σ
{\displaystyle \sigma }
and polynomial
h
(
X
)
{\displaystyle h(X)}
over
K
{\displaystyle K}
the value of the polynomial
σ
(
h
(
X
)
)
{\displaystyle \sigma (h(X))}
at a equals
σ
(
h
(
a
)
)
{\displaystyle \sigma (h(a))}
.
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.
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. Vol. 233. Cambridge University Press. ISBN 978-0-521-56736-7. Zbl 0851.00052.
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. hdl:1887/3824. JSTOR 2007886. Zbl 0615.12023.
Menezes, Alfred J., ed. (1993). Applications of finite fields. The Kluwer International Series in Engineering and Computer Science. Vol. 199. Boston: Kluwer Academic Publishers. ISBN 978-0792392828. Zbl 0779.11059.
Kata Kunci Pencarian:
- Matriks normal
- Perangkat lunak
- Pemantauan aktivitas basis data
- Plasmid
- Ambroksol
- Sistem imun
- Manchester United F.C.
- Kabupaten Bireuen
- Prion
- Metformin
- Normal basis
- Basis
- Normal
- Jordan normal form
- Canonical basis
- Itoh–Tsujii inversion algorithm
- Galois representation
- Normal extension
- Normal distribution
- Dual basis in a field extension
