量子計算によるECDLPの効率的解法について

スポンサーリンク

概要

論文の詳細を見る
量子計算の分野において最も衝撃的だったのは、1994年のShorによる素因数分解問題、及び有限体上の離散対数問題が多項式時間で解けるという結果であった。ここで、我々は、はたしてShorのアルゴリズムが楕円曲線上の離散対数問題にもそのまま適用できるのかという問題を考えてみる。本論文では、実際に楕円曲線上の離散対数問題に対するShorのアルゴリズムを明確に記述することで、難なく適用できることを確認する。更に、Shorのアルゴリズム以外に、Kitaevのアルゴリズムを用いることでも楕円曲線上の離散対数問題を多項式時間で解くことが可能である。従って、楕円曲線上の離散対数問題に対するKitaevのアルゴリズムを考察することも本稿の目的としている。
1999-09-24

著者

関連論文

もっと見る

スポンサーリンク