Cryptography Reference
In-Depth Information
First, we find some “systematic equations”. We obviously have the relation
x
15
=
+
x
1.
We also have (
x
+
1)
16
=
x
2
+
x
+
1 and (
x
3
+
x
+
1)
16
=
(
x
3
+
x
+
1)(
x
3
+
x
2
+
1).
√
5
≈
√
n/b
Now, we do Coppersmith's method. We must choose 2
k
=
≈
2
.
2so
take 2
k
n/
2
k
=
2. Let
l
=
=
8, choose
A
(
x
) and
B
(
x
)ofdegreeatmost2,set
A
(
x
)
x
8
C
(
x
)
2
C
(
x
)
=
+
B
(
x
) and
D
(
x
)
=
(mod
F
(
x
)) and test
C
(
x
) and
D
(
x
) for smooth-
ness over
B
. We find the following pairs (
A
(
x
)
,B
(
x
)) such that both
C
(
x
) and
D
(
x
) factor
over
B
.
A
(
x
)
B
(
x
)
C
(
x
)
D
(
x
)
1)
8
x
2
1
1
(
x
+
+
x
+
1
1)(
x
3
1)(
x
3
x
2
1
x
x
(
x
+
+
x
+
+
+
1)
x
x
2
x
2
(
x
1)
2
(
x
2
1)
2
x
(
x
3
1
+
+
x
+
+
x
+
1)
1)
16
x
2
The first relation in the table is a restatement of (
x
+
=
+
x
+
1. All together
we have the relation matrix
15
1000
0 6
−
10 0
00 0 5
−
1
12022
34 4
−
.
(15.10)
−
10
To solve the DLP one can now try to express
g
and
h
over the factor base. One has
g
22
1)(
x
2
1)
2
(
x
3
+
x
2
=
x
(
x
+
+
x
+
+
1)
.
For
h
we find
hg
30
x
6
(
x
1)
4
G
(
x
)
=
+
where
G
(
x
)
=
x
4
+
x
+
1
is
a
“large
prime”.
To
“smooth”
G
(
x
)
we
choose
A
(
x
)
=
1,
B
(
x
)
=
A
(
x
)
x
8
(mod
G
(
x
))
=
x
2
+
1,
C
(
x
)
=
A
(
x
)
x
8
+
B
(
x
)
and
D
(
x
)
=
C
(
x
)
2
G
(
x
)
2
1)(
x
3
x
2
(mod
F
(
x
)). One finds
C
(
x
)
=
and
D
(
x
)
=
(
x
+
+
+
1). In other
words,
G
(
x
)
4
1)(
x
3
x
2
1).
There are now two ways to proceed. Following the algorithm description above we
add to the matrix the two rows (1
,
1
,
2
,
0
,
1) and 4(6
,
4
,
0
,
0
,
0)
=
(
x
+
+
+
=
(24
,
17
,
0
,
0
,
1) corresponding to
g
22
and
h
4
g
120
. Finding a non-trivial kernel vector modulo
151, such as (1
,
114
,
0
,
132
,
113
,
133
,
56) gives the relation
+
(0
,
1
,
0
,
0
,
0
,
1)
(
g
22
)
133
(
h
4
g
120
)
56
g
133
h
73
1
=
=
g
23
.
An alternative approach to the linear algebra is to diagonalise the system in equa-
tion (
15.10
) using linear algebra over
from which we deduce
h
=
(or at least modulo 2
15
Z
−
1) to get
x
+
1
=
x
15
,x
2
x
240
,x
3
x
1023
and
x
3
x
2
x
15345
. One then gets
+
x
+
1
=
+
x
+
1
=
+
+
1
=
g
22
1)(
x
2
1)
2
(
x
3
x
2
x
1
+
15
+
2
·
240
+
15345
x
15841
=
x
(
x
+
+
x
+
+
+
1)
=
=
