離散対数
代数学における離散対数(りさんたいすう、英: discrete logarithm)とは、通常の対数の群論的な類似物である。 離散対数を計算する問題は整数の因数分解と以下の点が共通している:
両方とも難しい(量子コンピュータ以外では効率的に解くアルゴリズムが得られていない)
片方に対するアルゴリズムはしばしばもう片方にも利用できる
問題の困難性が暗号系の構築に利用されている
一般に、G を位数 n の有限巡回群とする(群は乗法的に書かれているものとする)。b を G の生成元とすれば、G の任意の元 g は、適当な整数 k を用いて g = b の形に書ける。さらに、g を表現する二つの整数 k1, k2 は必ず n を法として合同である。したがって、g に n を法とする k の合同類を対応させることにより
log b : G → Z / n Z {\displaystyle \log _{b}\colon G\to \mathbb {Z} /n\mathbb {Z} }
なる函数を定義することができる。ここで Z/nZ は n を法とする整数の剰余類環である。この関数は群同型写像であり、b を底とする離散対数と呼ばれる。
通常の対数と同様の底の変換公式が、c を G の別の生成元として
log c  ( g ) = log c  ( b ) ⋅ log b  ( g ) {\displaystyle \log _{c}(g)=\log _{c}(b)\cdot \log _{b}(g)}
が成立するという意味で有効である。