Theorem 20.16. If ± ∈ E — has multiplicative order r, then the degree of ±

over F is equal to the multiplicative order of q modulo r.

458 Finite ¬elds

Let us de¬ne the polynomial

’1

(X ’ σ i (±)).

χ :=

i=0

It is easy to see, using the same type of argument as above, that χ ∈ F [X],

and indeed, that

/k

χ=φ .

The polynomial χ is called the characteristic polynomial of ± (from E

to F ).

Two functions that are often useful are the “norm” and “trace.” The

norm of ± (from E to F ) is de¬ned as

’1

σ i (±),

NE/F (±) :=

i=0

while the trace of ± (from E to F ) is de¬ned as

’1

σ i (±).

TrE/F (±) :=

i=0

It is easy to see that both the norm and trace of ± are elements of F ,

as they are ¬xed by σ; alternatively, one can see this by observing that

they appear, possibly with a minus sign, as coe¬cients of the characteristic

polynomial χ ” indeed, the constant term of χ is equal to (’1) NE/F (±),

and the coe¬cient of X ’1 in χ is ’TrE/F (±).

The following two theorems summarize the most important facts about

the norm and trace functions.

Theorem 20.17. The function NE/F , restricted to E — , is a group homo-

morphism from E — onto F — .

Proof. We have

’1

’1 i

qi

P

’1)/(q’1)

i=0 q = ±(q

NE/F (±) = ± =± .

i=0

Since E — is a cyclic group of order q ’ 1, the image of the (q ’ 1)/(q ’ 1)-

power map on E — is the unique subgroup of E — of order q ’ 1 (see Theo-

rem 8.31). Since F — is a subgroup of E — of order q ’ 1, it follows that the

image of this power map is F — . 2

Theorem 20.18. The function TrE/F is an F -linear map from E onto F .

20.4 Conjugates, norms and traces 459

Proof. The fact that TrE/F is an F -linear map is a simple consequence of

the fact that σ is an F -algebra automorphism (verify). As discussed above,

TrE/F maps into F . Since the image of TrE/F is a subspace of F , the image

is either {0} or F , and so it su¬ces to show that TrE/F does not map all of

E to zero. But an element ± ∈ E is in the kernel of TrE/F if and only if ±

is a root of the polynomial

’1

X + Xq + · · · + Xq ,

which has degree q ’1 . Since E contains q elements, not all elements of E

can lie in the kernel of TrE/F . 2

Example 20.1. As an application of some of the above theory, let us in-

vestigate the factorization of the polynomial Xr ’ 1 over F , a ¬nite ¬eld of

cardinality q. Let us assume that r > 0 and is relatively prime to q. Let

E be a splitting ¬eld of Xr ’ 1 (see Theorem 17.19), so that E is a ¬nite

extension of F in which Xr ’ 1 splits into linear factors:

r

r

X ’1= (X ’ ±i ).

i=1

We claim that the roots ±i of Xr ’ 1 are distinct ” this follows from the

Theorem 20.4 and the fact that gcd(Xr ’ 1, rXr’1 ) = 1.

Next, observe that the r roots of Xr ’ 1 in E actually form a subgroup

of E — , and since E — is cyclic, this subgroup must be cyclic as well. So the

roots of Xr ’ 1 form a cyclic subgroup of E — of order r. Let ζ be a generator

for this group. Then all the roots of Xr ’ 1 are contained in F [ζ], and so we

may as well assume that E = F [ζ].

Let us compute the degree of ζ over F . By Theorem 20.16, the degree

of ζ over F is the multiplicative order of q modulo r. Moreover, the φ(r)

roots of Xr ’1 of multiplicative order r are partitioned into φ(r)/ conjugacy

classes, each of size ; indeed, as the reader is urged to verify, these conjugacy

classes are in one-to-one correspondence with the cosets of the subgroup of

Z— generated by [q]r , where each such coset C ⊆ Z— corresponds to the

r r

a : [a] ∈ C}.

conjugacy class {ζ r

More generally, for any s | r, any root of Xr ’ 1 whose multiplicative order

is s has degree k over F , where k is the multiplicative order of q modulo

s. As above, the φ(s) roots of multiplicative order s are partitioned into

φ(s)/k conjugacy classes, which are in one-to-one correspondence with the

cosets of the subgroup of Z— generated by [q]s .

s

This tells us exactly how Xr ’ 1 splits into irreducible factors over F .

Things are a bit simpler when r is prime, in which case, from the above

460 Finite ¬elds

discussion, we see that

(r’1)/

Xr ’ 1 = (X ’ 1) fi ,

i=1

where each fi is an irreducible polynomial of degree , and is the multi-

plicative order of q modulo r.

In the above analysis, instead of constructing the ¬eld E using Theo-

rem 17.19, one could instead simply construct E as F [X]/(φ), where φ is any

irreducible polynomial of degree , and where is the multiplicative order

of q modulo r. We know that such a polynomial φ exists by Theorem 20.11,

and since E has cardinality q , and r | (q ’ 1) = |E — |, and E — is cyclic, we

know that E — contains an element ζ of multiplicative order r, and each of

the r distinct powers of ζ are roots of Xr ’ 1, and so this E is a splitting

¬eld Xr ’ 1 over F . 2

Exercise 20.5. Let E be a ¬nite extension of a ¬nite ¬eld F . Show that

for a ∈ F , we have NE/F (a) = a and TrE/F (a) = a.

Exercise 20.6. Let E be a ¬nite extension of a ¬nite ¬eld F . Let E be an

intermediate ¬eld, F ⊆ E ⊆ E. Show that

(a) NE/F (±) = NE /F (NE/E (±)), and

(b) TrE/F (±) = TrE /F (TrE/E (±)).

Exercise 20.7. Let F be a ¬nite ¬eld, and let f ∈ F [X] be a monic irre-

ducible polynomial of degree . Let E = F [X]/(f ) = F [·], where · := [X]f .

(a) Show that

∞

D(f )

TrE/F (· j’1 )X’j .

=

f

j=1

(b) From part (a), deduce that the sequence

TrE/F (· j’1 ) (j = 1, 2, . . .)

is linearly generated over F with minimal polynomial f .

(c) Show that one can always choose a polynomial f so that sequence in

part (b) is purely periodic with period q ’ 1.

Exercise 20.8. Let F be a ¬nite ¬eld, and f ∈ F [X] an irreducible polyno-

mial of degree k over F . Let E be an extension of degree over F . Show

that over E, f factors as the product of d distinct irreducible polynomials,

each of degree k/d, where d = gcd(k, ).

20.4 Conjugates, norms and traces 461

Exercise 20.9. Let E be a ¬nite extension of a ¬nite ¬eld F of characteristic