Lattice Basis Reduction

296 Lattice Basis Reduction

Exercise 15.6. Rec all that F

×

q

is the multiplicative group of nonzero elements

in the field F

q

with q elements. Let S = {a

2

| a ∈ F

×

q

} be the set of squares

in F

×

q

. Verify the following claims for q = 3, q = 5, q = 7, q = 9, and q = 11:

(a) S is a subgroup of F

×

q

of order (q−1)/2.

(b) S = {a ∈ F

×

q

| a

(q−1)/2

= 1 }.

(c) For every a ∈ F

×

q

we have a

(q−1)/2

= ±1.

Exercise 15.7. Let p be a prime numbe r, and let h = x

p

− x in F

p

[x].

(a) Determine the factorization h = h

e

1

1

h

e

2

2

···h

e

ℓ

ℓ

where h

1

, h

2

, . . . , h

ℓ

are

distinct monic irreducible polynomials.

(b) Explain why the Chinese Remainder Theorem gives an isomorphism

φ: F

p

[x]/hhi → F

p

[x]/hh

e

1

1

i × F

p

[x]/hh

e

2

2

i × ··· × F

p

[x]/hh

e

ℓ

ℓ

i.

(c) Determine explicitly each factor on the right side of