Cryptography Reference
In-Depth Information
=
(
)
order
p
i
. Since
e
i
, this implies that the running time of the algorithm to
compute discrete logarithms in
G
can be improved to
O
O
ln
n
max
i
(
√
p
i
)
·
(
(
))
.
This is the reason why a necessary condition for the DLP to be difficult is that the
order of
G
should have a large prime factor. We shall not go into the details of this
further reduction for which we refer the interested reader to [43, 102, 193].
polylog
n
6.5.4.1 The Pohlig-Hellman Algorithm in Maple
We next implement the Pohlig-Hellman algorithm in Maple with the option of using
either BSGS or the rho method, which will allow us to compute discrete logarithms
in groups of large order whose prime factors are relatively small. We will just use
the CRT reduction modulo prime powers, which is sufficient to compute discrete
logarithms in
Z
p
for typical prime moduli
p
of relatively large size.
The
PohligHellman
function has the same input parameters as the previous
function
RhoDiscreteLog
, plus an optional keyword parameter
method
which
is used to specify which method is used to compute the discrete logarithms. The
values accepted by this parameter are
method = Rho
and
method= BSGS
, with
the former being the default. The output is, assuming that
a
∈
g
, the discrete
∈ Z
m
.
> PohligHellman := proc(m::posint, g::posint, a::posint,
n::posint := numtheory:-order(g, m), {method::name:=Rho})
local facts, i, exps, glist, alist, xlist;
if igcd(m, g) <> 1 then
error "%1 is not a unit modulo %2", g, m
end if;
if igcd(m, a) <> 1 then
error "%1 is not a unit modulo %2", a, m
end if;
if n < 1000000 then
return BSGS(m, g, a)
end if;
facts := ifactors(n)[2];
facts := map(l -> l[1]ˆl[2], facts);
exps := n/
∼
(facts);
glist := Power
∼
(g, exps) mod m;
alist := Power
∼
(a, exps) mod m;
if method = Rho then
xlist := RhoDiscreteLog
∼
(m, glist, alist, facts)
else
xlist := BSGS
∼
(m, glist, alist, facts)
end if;
chrem(xlist, facts)
end proc:
logarithm of
a
to the base
g
Example 6.27
We use the same elements as in some previous examples for BSGS
and the rho method:
> p := 439809843839:
g := 139046225820:
a := 310669347635:
PohligHellman(p, g, a, method = BSGS);
54679028452
