離散対数 アルゴリズム

ウィキペディア

離散対数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 06:40 UTC 版)

アルゴリズム

群 $G$ における離散対数 $\log _{b}g$ を計算する効率の良いアルゴリズムは知られていない。 ナイーブなアルゴリズムとしては、$b$ の1乗、2乗、3乗、…を順に計算し、 求める $g$ が得られるまで続ける方法がある。 このアルゴリズムは $G$ の位数について線形な、すなわち要素の桁数（特に、何ビットか）について指数的な実行時間を要し、 巨大な $G$ に対して実用的でない。

より高度なアルゴリズムも知られており、代表的なものを以下に挙げる。 整数の因数分解アルゴリズムと同様のアイディアが多い。 これらは上記のナイーブなアルゴリズムより高速であるものの、多項式時間では計算が終わらない。

• ベビーステップジャイアントステップ
• ポラード・ロー離散対数アルゴリズム
• ポラード・ラムダアルゴリズム（「ボラード・カンガルー・アルゴリズム」とも呼ばれる）
• ポーリヒヘルマンアルゴリズム
• インデックス計算アルゴリズム
• 数体篩法
• 函数体篩法

一方、量子コンピュータ上で動作する効率的な量子アルゴリズムがピーター・ショアによって与えられている。