Lattice Basis Reduction

Polynomial Factorization 271

It follows that the two inequalities must be equalities. In particular, the kernel

has 2 elements, which proves (a). Furthermore, S has e elements, and so it

equals the kernel of the e-power map, which proves (b). Finally, we see that

the image of the e-power map has two elements; it clearly contains ±1, and

these elements are distinct since p 6= 2, and which proves (c).

Let q = p

n

(p 6= 2). Suppose that d ≥ 1 and that h ∈ F

q

[x] has ℓ ≥ 2

distinct monic irreducible factors each of degree d:

h =

ℓ

Y

j=1

h

j

, deg(h

j

) = d, deg(h) = dℓ.

We consider the quotient ring F

q

[x]/hhi. Since h

1

, h

2

, . . . , h

ℓ

are relatively

prime, the Chinese ...