GF(Q)上の対数計算アルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• PohligとHellmanは,Q-1が小さな素因数のみを持つ場合,O(log_2 Q)^2の計算量と,O(log_2 Q)bitの記憶容量を必要とするGF(Q)上の対数計算アルゴリズムを発表している.このアルゴリズムを改良し,O(c(log_2 Q)(log_2log_2 Q))の計算量と,O(d(log_2Q)(log_2log_2 Q))bitの記憶容量で対数計算を実行できるアルゴリズムを提案する(c,dは定数).

• 一般社団法人情報処理学会の論文
• 1987-02-15

著者

• 八木沢 正博

  昭和エンジニアリング(株)

関連論文

• 素因数分解問題に基づく公開鍵暗号系
• 一次不定方程式に基づくゼロ知識対話証明
• 限定されたデイオファンタス不定方程式の解を効率的に算出するアルゴリズム
• ディオファンタスの一次不定方程式に基づく公開鍵暗号系
• 離散的対数問題に基づく公開鍵暗号系
• GF(Q)上の対数計算アルゴリズム

スポンサーリンク