文献

J-GLOBAL ID：202002268010923558   整理番号：20A2516933

ECDLPのためのSemaevのナイーブインデックス計算法に関する計算量限界【JST・京大機械翻訳】

Complexity bounds on Semaev’s naive index calculus method for ECDLP

著者 (4件)： Yokoyama Kazuhiro (Rikkyo University, Tokyo, Japan) ,  Yasuda Masaya (Rikkyo University, Tokyo, Japan) ,  Takahashi Yasushi (FUJITSU Laboratories LTD., Kawasaki, Japan) ,  Kogure Jun (FUJITSU Laboratories LTD., Kawasaki, Japan)
資料名： Journal of Mathematical Cryptology  (Journal of Mathematical Cryptology)
巻： 14  号： 1  ページ： 460-485  発行年： 2020年 
JST資料番号： W3808A  ISSN： 1862-2976  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： Semaevは2004年に加算多項式を導入したので,Pollard rho法やベビーステップ法や巨大ステップ法(BSGS)のような一般的な方法よりも,楕円曲線離散対数問題(ECDLP)を解くための指数計算法の改善に多くの研究が払われてきた。本論文では,Semaevのナイーブインデックス計算法における点分解問題(PDP)に現れる多項式システムを解くためのGrobner基底計算の深い解析を提供した。著者らの解析は,加算多項式に関する単純な統計的仮定の下で線形代数に依存する。PDPから導出された理想は特殊構造を持ち,理想に対するGrobner基底計算は拡張ユークリッドアルゴリズムの拡張と見なされることを示した。これによりGrobnerベース計算のコストに下限を得ることができる。下限で,著者らは,ナイーブインデックス計算法が一般的方法よりも効率的でないことを証明した。Please refer to the publisher for the copyright holders. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 多項式 ,  基底 ,  線形代数 ,  *計算量 ,  加算
準シソーラス用語： 楕円曲線 ,  離散対数問題 , 【Automatic Indexing@JST】

著者キーワード (2件)： 一次94A60 ,  二次14G50

分類 (1件)： 符号理論  (ND02030R)

タイトルに関連する用語 (3件)： 計算法 ,  計算量 ,  限界