Lattice Basis Reduction

276 Lattice Basis Reduction

g

1

, h

1

∈ Z[x] such that

f = g

1

h

1

in F

p

[x] and this factorization is proper in

the sense that neither g

1

nor h

1

is a constant. (We also need to assume tha t

g

1

and h

1

are relatively prime in F

p

[x], but we ignore this for the moment.)

We want to lift this factorization from the modulus p to the mo dulus p

2

: that

is, we want to find polynomials g

2

, h

2

∈ Z[x] s uch that deg(g

1

) = deg(g

2

),

deg(h

1

) = deg(h

2

), and f ≡ g

2

h

2

(mod p

2

). In other words, we want to lift

the factorization from the polynomial ring (Z/pZ)[x] to the po lynomial ring

(Z/p

2

Z)[x]. It is important to realize that Z/p

2

Z is not a field, so in particular

it is not is omorphic ...