著者

山道 将人 満保 雅浩 静谷 啓樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. ISEC, 情報セキュリティ

巻号頁・発行日

vol.99, no.414, pp.51-58, 1999-11-08

---

有限体上の楕円曲線の位数は多項式時間で計算できることがSchoofにより示されたが,逆に,与えられた位数を持つ有限体上の楕円曲線を多項式時間で計算できるかどうかは1986年以来の未解決問題である.本論文ではこの未解決問題に関して,与えられた位数を持つ楕円曲線を求める多価部分関数fの難しさの特徴付けを行う.その結果,もしブール式を充足させる割り当てを一つ出力する多価部分関数satがfに多項式時間Turing帰着するならば,多項式時間階層がNPまで潰れることを示す.また拡張Riemann予想の仮定のもとで,この未解決問題と等価な問題を示す.