A study on the probabilistic algorithm to solve the elliptic curve discrete logarithm problem

摘要

In this paper a probabilistic algorithm to solve the ECDLP is presented. This scheme uses the symmetry of the elliptic curve, and can be applied to a wide class of elliptic curves. In the proposed scheme a large number of random integers H_i ∈ {0, 1, ···, g-1} (i = 1,2, ···) are generated to calculate the points Q + H_i P (i = 1,2, ··, where Q = K_(secret)P and g is the order of the point P. Then, the scheme tries to find a pair of points Q -f HiP and Q + H_jP whose X-coordinates are the same value but Hi ≠ H_j, i.e., one in the pair is the inverse of the other. If such a pair is found, the secret Ksecret can be calculated by 2K_(secret) + H_i + H_j ≡ 0 (mod g). We investigate the probability to find such a pair among m random points on an elliptic curve. The probability of finding one or more pairs would be 1/2 when m is of the order of g~(1/2). Furthermore, we discuss the techniques to reduce the size of disk storage and to parallelize the operation with multiple computers. It is also shown that the proposed algorithm can be extended to solve the usual discrete logarithm problem (DLP).