- 著者
-
四方 順司
鈴木 譲
今井 秀樹
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. ISEC, 情報セキュリティ (ISSN:09135685)
- 巻号頁・発行日
- vol.99, no.329, pp.9-15, 1999-09-24
量子計算の分野において最も衝撃的だったのは、1994年のShorによる素因数分解問題、及び有限体上の離散対数問題が多項式時間で解けるという結果であった。ここで、我々は、はたしてShorのアルゴリズムが楕円曲線上の離散対数問題にもそのまま適用できるのかという問題を考えてみる。本論文では、実際に楕円曲線上の離散対数問題に対するShorのアルゴリズムを明確に記述することで、難なく適用できることを確認する。更に、Shorのアルゴリズム以外に、Kitaevのアルゴリズムを用いることでも楕円曲線上の離散対数問題を多項式時間で解くことが可能である。従って、楕円曲線上の離散対数問題に対するKitaevのアルゴリズムを考察することも本稿の目的としている。