Cryptography Reference
In-Depth Information
1 then one can multiply
F
(
x
)by
a
−
d
(mod
M
) to make it monic.
If gcd(
a
d
,M
)
>
1 then one can split
M
and reduce the problem to two (typically easier)
problems. As explained above, to find
x
0
it will be sufficient to find a polynomial
G
(
x
) with
the same root
x
0
modulo
M
but with sufficiently small coefficients.
To do this, consider the
d
monic but gcd(
a
d
,M
)
=
Mx
i
for 0
+
1 polynomials
G
i
(
x
)
=
≤
i<d
and
F
(
x
). They
all have the solution
x
x
0
modulo
M
. Define the lattice
L
with basis corresponding to
these polynomials (by associating with a polynomial the row vector in equation (
19.1
)).
Therefore, the basis matrix for the lattice
L
is
=
M
0
···
0
0
0
MX
···
0
0
.
.
.
B
=
.
(19.2)
MX
d
−
1
00
···
0
a
d
−
1
X
d
−
1
X
d
a
0
a
1
X
···
Every element of this lattice is a row vector that can be interpreted as a polynomial
F
(
x
)
(via equation (
19.1
) such that
F
(
x
0
)
≡
0(mod
M
).
Lemma 19.1.3
The dimension of the lattice L defined in equation (
19.2
) above is d
+
1
and the determinant is
M
d
X
d
(
d
+
1)
/
2
.
det(
L
)
=
Exercise 19.1.4
Prove Lemma
19.1.3
.
One now runs the LLL algorithm on this (row) lattice basis. Let
G
(
x
) be the polynomial
corresponding to the first vector
b
1
of the LLL-reduced basis (since every row of
B
has the
form of equation (
19.1
) then so does
b
1
).
Theorem 19.1.5
Let the notation be as above and letG
(
x
)
be the polynomial corresponding
to the first vector in the LLL-reduced basis for L. Set c
1
(
d
)
2
−
1
/
2
(
d
1)
−
1
/d
.IfX<
=
+
c
1
(
d
)
M
2
/d
(
d
+
1)
then any root x
0
of F
(
x
)
modulo M such that
|
x
0
|≤
X satisfies G
(
x
0
)
=
0
in
Z
.
Proof
Recall that
b
1
satisfies
2
(
n
−
1)
/
4
det(
L
)
1
/n
2
d/
4
M
d/
(
d
+
1)
X
d/
2
.
b
1
≤
=
<M/
√
d
For
b
1
to satisfy the conditions of Howgrave-Graham's theorem (i.e.,
b
1
+
1)
it is sufficient that
2
d/
4
M
d/
(
d
+
1)
X
d/
2
<M/
√
d
+
1
.
This can be written as
√
d
12
d/
4
X
d/
2
<M
1
/
(
d
+
1)
,
+
which is equivalent to the condition in the statement of the theorem.
