Lattice Basis Reduction

Polynomial Factorization 281

Modulo 625

2

= 390625 we obtain

g

4

= x

2

+ 390622x + 2, h

4

= x

2

+ 390618x + 12,

together with

s

4

= 130208x + 195314, t

4

= 260417x + 65104.

Modulo 390625

2

= 1525878906 25 we obtain

g

5

= x

2

+ 152587890622 x + 2, h

5

= x

2

+ 152587890618 x + 12,

together with

s

5

= 50862630208x + 762939 45314, t

5

= 101725260417x + 25431 315104.

Theorem 15.21. Hensel’s Lem ma. Let p be a prime number. Let

f, g

1

, h

1

, s

1

, t

1

∈ Z[x] be such that h

1

is monic and

f ≡ g

1

h

1

(mod p), deg(f ) = deg(g

1

) + deg(h

1

),

s

1

g

1

+ t

1

h

1

≡ 1 (mod p), deg(s

1

) < deg(h

1

), deg(t

1

) < deg(g

1

).

Then for any n ≥ 1 there exist g

n

, h

n

, s

n

, t

n

∈ Z[x] such that h

n

is monic and

f ≡ g

n

h

n



mod p

2

n



, g

n

≡ g

1

(mod ...