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

If the number of divisors is small, as usually happens in the case of cryptographic
applications in which either

| ( F p ) |

is prime (which automatically gives the order
of any nonzero point) or has a large prime factor, then the computation of the point
order becomes easy. In the ECDLP problem, even if the order of the point and its
factorization are known, we cannot apply this shortcut and have to run through all
the possible values 1

E

in succession, as it is obvious that any of them might
be the discrete log we are looking for. Thus the brute-force algorithm takes O

, 2 ,...

( n )

steps and it will require approximately n steps in the worst case and n 2 steps on

average. Hence the running time is exponential on the size of n and it suffices to take
n to be about 100 bits long to make this computation infeasible in practice. Although
there are more efficient algorithms for the ECDLP (the collision-based algorithms
mentioned below) we stress that, in contrast with the computation of the order, the
ECDLP problem is thought to be (very) hard in general, and even more so if the
group order is prime.
The generic algorithms to solve the ECDLP are, as a direct consequence of the very
definition of generic , the same as those we studied in Sect. 6.5 . These are collision-
based algorithms su c h as the baby step-giant stepmethod and Pollard 's rho algorithm,
which require O

/

( √ n ( √ q

to solve it in a
subgroup of order n —and hence, while faster than brute force, still run in exponential
time.

) steps to solve the ECDLP in E ( F q ) —or O )

11.3.1 The Rho Method and Pohlig-Hellman for the ECDLP
in Maple

In order to appreciate how the collision-based algorithms work in the elliptic curve
case, we next give a Maple implementation of the one which is probably the fastest of
them, namely, Pollard's rho. We take the function RhoDiscreteLog of Sect. 6.5
and translate it to the elliptic curve setting. The translation is straightforward since
it essentially consists of replacing the modular exponentiations used to compute
powers of elements in subgroups of

Z m by multiplications of points by integers in

subgroups of E (in consonance with our previous implementation of elliptic

curve algorithms, we will restrict ourselves to elliptic curves defined over prime
fields).
In theMaple function implementing the rho method we are going to use a partition
of the group

( F p )

into three subsets similar to the one originally suggested by Pollard,
using here the x -coordinate of the point to obtain a partition according to its size. We
remark, however, that many other random-like partitions of this group into subsets
of roughly the same size are possible and that it is common to select a larger number
of subsets or branches , typical numbers being 16 and 32. For example, to obtain 32
branches, the points of

P

can be partitioned according to the five least significant
bits of the x -coordinates as suggested in [97].

P