講演抄録/キーワード |
講演名 |
2009-03-10 15:40
代数的トーラス上の離散対数問題に関する計算量理論的考察 ○西垣裕次・長谷川真吾・磯辺秀司・小泉英介・酒井正夫・静谷啓樹(東北大) IT2008-127 ISEC2008-185 WBS2008-140 |
抄録 |
(和) |
本稿では, 代数的トーラス上の離散対数問題(TDLP)を計算量理論の立場から考察する.得られた主な結果は次のとおりである.
(1)代数的トーラスは計算可能な群である.
(2)TDLPはNPとcoNPの共通部分に属する言語に多項式時間で帰着する.
(3)底の位数に関する証明の付いた離散対数問題はTDLPを変形した問題の一つひ多項式時間で帰着する. |
(英) |
In this paper we investigate the computational complexity of the discrete logarithm problem over algebraic tori (TDLP).
We show that
(i) each algebraic torus is a computational group,
(ii) TDLP reduces in polynomial time to a set in the intersection of NP and coNP, and
(iii) the order-certified discrete logarithm over a finite field reduces in polynomial to a variation of TDLP. |
キーワード |
(和) |
代数的トーラス / 離散対数問題 / 計算量理論 / / / / / |
(英) |
Algebraic Tori / Discrete Logarithm Problem / Computational Complexity Theory / / / / / |
文献情報 |
信学技報, vol. 108, no. 473, ISEC2008-185, pp. 545-550, 2009年3月. |
資料番号 |
ISEC2008-185 |
発行日 |
2009-03-02 (IT, ISEC, WBS) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2008-127 ISEC2008-185 WBS2008-140 |