巡回群 $\langle g \rangle$ と $y\in \langle g \rangle$ に対して、 $g^x = y$ となる整数 $x$ を求める問題。

• $g$ を 底 (base)、$x$ を 離散対数 と呼ぶ。
• 公開鍵暗号の基盤になる
  • 順方向 $x \mapsto g^x$ は 繰り返し二乗法 で $O(\log x)$
  • 逆方向 $y \mapsto x$ は、群の取り方によっては効率的なアルゴリズムが知られていない
  • この 一方向性 (one-way) が暗号の安全性を支える