Cryptography Reference
In-Depth Information
=
Input
:
g
and
y
in a group
G
,#
G
N
and the complete factorization
p
a
1
1
N
=
...
p
a
n
n
such that
p
i
is prime,
p
1
=
p
j
, and
a
i
>
0 for 1
≤
j
Output
: the logarith
m o
f
y
in base
g
Complexity
:
i
,
j
≤
n
and
i
=
(
a
1
√
p
1
+···+
a
n
√
p
n
) group operations
O
1:
for
i
=
1
,...,
n
do
g
N
/
p
a
i
g
←
2:
i
g
p
a
i
−
1
g
←
3:
i
y
N
/
p
a
i
y
←
4:
i
y
←
y
5:
x
i
←
0
6:
for
j
=
0to
a
i
−
1
do
7:
y
p
a
i
−
j
−
1
y
←
8:
i
compute the discrete logarithm
u
of
y
in the subgroup of order
p
i
which is spanned by
g
9:
g
u
.
p
i
y
←
y
/
10:
p
i
x
i
←
x
i
+
u
.
11:
12:
end for
13:
end for
14:
reconstruct and yield
x
such that
x
x
i
(mod
p
a
i
)
≡
Figure 7.10.
Pohlig-Hellman Algorithm.
mod
p
y
p
−
2
.Wehave
Let us first compute
log
g
p
−
1
2
g
p
−
1
y
p
−
1
6
62825
123
62825
mod
p
=
mod
p
=
125650
,
mod
p
=
mod
p
=
125650
.
2
2
Therefore
y
p
−
2
log
g
p
−
1
2
=
1
.
mod
p
y
p
−
7
.Wehave
Let us now compute
log
g
p
−
1
7
mod
p
p
−
1
p
−
1
6
17950
123
17950
g
mod
p
=
mod
p
=
21153
,
y
mod
p
=
mod
p
=
91649
7
7
so we need to compute
log
21153 mod
p
(91649)
in a group of order 7. Since 7 is quite small,
we can exhaust all powers.
21153
0
mod
p
=
1
21153
1
mod
p
=
21153
21153
2
mod
p
=
6198
Search WWH ::
Custom Search