Fields - Elliptic Curves: Number Theory and Cryptography - page 481

F q ,then PROOF By Lagrange's theorem (see Appendix B), if μ m ⊆

1. Since F q m 1, it

has a subgroup of order m (see Appendix B). By Lagrange's theorem, the
elements of this subgroup must satisfy x m

| q − 1. Conversely, suppose m | q − is cyclic of order q −

= 1, hence they must be the m

elements of μ m .

Let F q ⊆ F q n be finite fields. We can regard F q n as a vector space of
dimension n over F q . This means that there is a basis {β 1 ,...,β n } of elements
of F q n such that every element of F q n has a unique expression of the form

a 1 β 1 + ··· + a n β n

with a 1 ,...,a n ∈ F q . The next result says that it is possible to choose a basis
of a particularly nice form, sometimes called a normal basis .

PROPOSITION C.4
There exists β ∈ F q n such that

{β, φ q ( β ) ,...,φ n− 1 ( β ) }

q

is a basis of F q n as a vector space over F q .

An advantage of a normal basis is that the q th power map becomes a shift
operator on the coordinates: Let

x = a 1 β + a 2 φ q ( β )+ ··· + a n φ n− 1 ( β ) ,

q

F q .Then a i

= a i and φ q ( β )= β ,so with a i ∈

x q = a 1 β q + a 2 φ q ( β q )+ + a n φ n− q ( β q )

= a n φ q ( β )+ a 1 φ q ( β )+ ··· + a n− 1 φ n− 1

···

( β )

q

= a n β + a 1 φ q ( β )+ ··· + a n− 1 φ n− 1 ( β ) .

q

Therefore, if x has coordinates ( a 1 ,...,a n ) with respect to the normal basis,
then x q has coordinates ( a n ,a 1 ,...,a n− 1 ). Therefore, the computation of
q th powers is very fast and requires no calculation in F q n . This has great
computational advantages.

Embeddings and automorphisms

Let K be a field of characteristic 0, so Q ⊆ K .Anelement α ∈ K is
called transcendental if it is not the root of any nonzero polynomial with