楕円離散対数問題の解法

楕円曲線上の離散対数問題は,楕円曲線上の 2点 $P$,$Q$ に関する式,

$Q = x P$

において,$Q$ から自然数 $x\ (1 \le x \le r,\ r$ は $P$ の位数) をを求める問題である.

ここで,$P$ は既知とし,$x P$ は $P$ をスカラー倍する演算である.

総当たり法

総当たり法 (Brute force method) は,楕円離散対数問題を解くのに,

$2P,\ 3P,\ \ldots,\ (r-1)P$

を順番に計算していく方法である.$mP$ が $Q$ に一致するような $m\ (2, 3, \ldots, r-1)$ が見つかるまで繰り返す.

BSGS 法

ρ

inserted by FC2 system