Elliptic Curve Discrete Logarithms and Wieferich Primes

概要

論文の詳細を見る
Recently, a new method, called by Xedni calculus, to solve ECDLP was proposed by Silverman and Kim et.al. [11, 5]. The Xedni addresses a novel idea, but has two difficulties. One is to find good liftings and the other is to compute the dependence relation among lifted rational points. In this paper, we propose a fast algorithm to compute the dependence relation modulo the order, n_<P^^〜>, of P^^〜 for given two dependent rational points of elliptic curve ober Q. Using this, if we could find liftings P, Q and E with rank 1 of P^^〜, Q^^〜, E^^〜, then we can solve the ECDLP very fast. Moreover, by this algorithm, we can easily check whether two lifted points are linearly independent or not. Also we investigate the possibility to get such liftings for elliptic curves with a non-trivial 2-torsion, and generate lots of liftings of rank ≤ 2.
社団法人電子情報通信学会の論文
2000-01-25