A NEW APPROACH TO THE PROBLEM OF TAKING DISCRETE LOGS ON AN ELLIPTIC CURVE

摘要

A new approach is suggested to treatment of the discrete logarithm problem in an Abelian group of points on an elliptic curve. The method is based on a procedure of dividing some subgroup of the curve points by two. In the event of proper selection of the division points, the algorithm leads to rapid definition of the discrete logarithm and the cryptosystem. The problems whose solution is equivalent to breaking the system are discussed. Cryptanalysis based on "collisions" using the division procedure supplemented by pseudorandom selection of points in a series of correct decisions leads us to a narrow segment of points where the probability of "collisions" exceeds that inherent in equiprobable subspaces of points.