An Introduction to Elliptic Curve Cryptography - Introduction to Cryptography with Maple - page 645

Consider now the point:

> Q1 := [6063899575093230643504690027823676167707218648228464374004,
5866884813689075251553628839257075615116374691273934221658]

We are given the information that Q 1 belongs to the subgroup generated by P 1
and the problem is to compute log P 1 Q 1. We do it as follows:
> EllipticRhoDiscreteLog(P1, Q1, ec192, oP1);
98765432101

11.3.1.1 The Pohlig-Hellman Algorithm in Maple

As we have seen in Sect. 6.5 , when the group order n is not prime there is a generic
algorithm (the Pohlig-Hellman algorithm) that essentially reduces the computation
of a discrete logarithm to the computation of discrete logarithms in subgroups whose
orders are the prime power factors (or even the prime factors) of n .Wehavealsoseen
that the run nin g time of the combination of the rho method with Pohlig-Hellman is

) , where the n i are the prime power factors of n , so that
the running time is dominated by the lar gest of these factors (and, in fact, the running

O max i ( √ n i ) ·

polylog ( n

time may be reduced to O max i √ p i · ) , where the p i are the distinct

polylog ( n

prime factors of n ).
These aspects make clear the convenience of using groups of prime order (or with
order equal to the product of a prime by a small integer) to make the DL problem
as hard as possible. All this applies entirely to the ECDLP and we may easily adapt
the Maple function PohligHellman given in Sect. 6.5 for this problem. In this
version we will not include the baby-step giant-step algorithm which is similarly
easy to translate to the elliptic setting, something that we will leave as an exercise.
The function EllipticPohligHellmanRho takes as input P , Q , E , n , where
P is a point of order n on the elliptic curve E and Q

∈ P , and computes log P Q :

> EllipticPohligHellmanRho := proc(P::{list(integer),identical(0)},
Q::{list(integer),identical(0)}, E::(list(integer)), n::integer)
local facts, mults, i, exps, Plist, Qlist, ordlist, xlist;
if E[3] < 100000 then
return EllipticRhoDiscreteLog(P, Q, E, n)
end if;
facts := ifactors(n)[2];
facts := map(l -> l[1]ˆl[2], facts);
mults := n/ ∼ (facts);
Plist := map(x -> EllipticMult(x, P, E), mults);
Qlist := map(x -> EllipticMult(x, Q, E), mults);
ordlist := map(x -> EllipticPointOrder(x, E, n), Plist);
xlist := [];
for i to nops(mults) do
xlist := [op(xlist), EllipticRhoDiscreteLog(Plist[i], Qlist[i], E, ordlist[i])]
end do;
chrem(xlist, facts)
end proc:

Example 11.19 We go back to the curve ec192 of Example 11.16 and show how the
preceding function allows us to compute a discrete logarithm in a large group whose
order is 191 bits long. We assume that the global variables ec192 and o192 still