Cryptography Reference
In-Depth Information
2.13 Hensel lifting
0(mod
p
e
),
Hensel lifting
is a tool for solving polynomial equations of the form
F
(
x
)
≡
where
p
is prime and
e
∈ N
>
1
. One application of Hensel lifting is the Takagi variant of
RSA, see Example
24.1.5
. The key idea is given in the following Lemma.
Lemma 2.13.1
Let F
(
x
)
∈ Z
[
x
]
be a polynomial andp a prime. Let x
k
∈ Z
satisfyF
(
x
k
)
≡
0(mod
p
k
)
where k
∈ N
. Suppose F
(
x
k
)
≡
0(mod
p
)
. Then one can compute x
k
+
1
∈ Z
≡
0(mod
p
k
+
1
)
.
in polynomial-time such that F
(
x
k
+
1
)
p
k
z
where
z
is a variable. Note that
F
(
x
k
+
1
)
0(mod
p
k
). One
Proof
Write
x
k
+
1
=
x
k
+
≡
has
p
k
F
(
x
k
)
z
(mod
p
k
+
1
)
.
F
(
x
k
+
1
)
≡
F
(
x
k
)
+
(
F
(
x
k
)
/p
k
)
F
(
x
k
)
−
1
0(mod
p
k
+
1
).
Setting
z
=−
(mod
p
)gives
F
(
x
k
+
1
)
≡
Example 2.13.2
We solve the equation
x
2
7(mod3
3
)
.
≡
x
2
x
2
Let
f
(
x
)
=
−
7. First, the equation
f
(
x
)
≡
−
1 (mod 3) has solutions
x
≡
1. Since
f
(1)
1
,
2(mod3).Wetake
x
1
=
=
2
≡
0 (mod 3), we can “lift” this to a solution
modulo 3
2
. Write
x
2
=
1
+
3
z
. Then
x
2
−
6
z
(mod 3
2
)
f
(
x
2
)
=
7
≡−
6
+
or, in other words, 1
−
z
≡
0 (mod 3). This has the solution
z
=
1giving
x
2
=
4.
Now lift to a solution modulo 3
3
. Write
x
3
=
72
z
(mod 3
3
)
4
+
9
z
. Then
f
(
x
3
)
≡
9
+
and dividing by 9 yields 1
−
z
≡
0 (mod 3). This has solution
z
=
1giving
x
3
=
13 as one
solution to the original equation.
Exercise 2.13.3
The equation
x
3
≡
3 (mod 5) has the solution
x
≡
2 (mod 5). Use Hensel
lifting to find a solution to the equation
x
3
3(mod5
3
).
≡
2.14 Algorithms in finite fields
We present some algorithms for constructing finite fields
F
p
m
when
m>
1, solving equa-
tions in them and transforming between different representations of them.
2.14.1 Constructing finite fields
Lemma
A.5.1
implies a randomly chosen monic polynomial in
F
q
[
x
]ofdegree
m
is
irreducible with probability
1
/
(2
m
). Hence, using the algorithm of Exercise
2.12.10
,
one can generate a random irreducible polynomial
F
(
x
)
≥
∈ F
q
[
x
]ofdegree
m
, using naive
arithmetic, in
O
(
m
4
log(
q
)) operations in
F
q
. In other words, one can construct a polynomial
F
q
m
in
O
(
m
4
log(
q
)) operations in
basis for
F
q
. This complexity is not the best known.
