離散対数
群 G {\displaystyle G} における離散対数 log b  g {\displaystyle \log _{b}g} を計算する効率の良いアルゴリズムは知られていない。 ナイーブなアルゴリズムとしては、 b {\displaystyle b} の1乗、2乗、3乗、...を順に計算し、 求める g {\displaystyle g} が得られるまで続ける方法がある。 このアルゴリズムは G {\displaystyle G} の位数について線形な、すなわち要素の桁数(特に、何ビットか)について指数的な実行時間を要し、 巨大な G {\displaystyle G} に対して実用的でない。
より高度なアルゴリズムも知られており、代表的なものを以下に挙げる。 整数の因数分解アルゴリズムと同様のアイディアが多い。 これらは上記のナイーブなアルゴリズムより高速であるものの、多項式時間では計算が終わらない。
ベビーステップジャイアントステップ(英語版)
ポラード・ロー離散対数アルゴリズム
ポラード・ラムダアルゴリズム(英語版)(「ボラード・カンガルー・アルゴリズム」とも呼ばれる)
ポーリヒヘルマンアルゴリズム(英語版)
インデックス計算アルゴリズム(英語版)
数体篩法(英語版)
函数体篩法(英語版)
一方、量子コンピュータ上で動作する効率的な量子アルゴリズムがピーター・ショアによって与えられている。