代数学における離散対数（りさんたいすう、）とは、通常の対数の群論的な類似物である。離散対数を計算する問題は整数の因数分解()と以下の点が共通している： 離散対数を理解するのに、最も簡単なのは素数 "p" を法とする整数の合同類からなる集合 {1, 2, ..., "p" − 1} に乗法を考えた (Z/"p"Z) であろう。この群の元の "k"-乗を知りたければ、普通の整数と看做して "k"-乗を求め、それから "p" で割った剰余（余り）を求めればよい（これを離散冪乗とよぶこともある）。例えば (Z/17Z) を考え、この中で 3 を計算するには、まず 3 = 81 としてから、81 を 17 で割って余りの 13 を得るので、既約剰余類群 (Z/17Z) の中で 3 ≡ 13 (mod 17) が成り立つ。離散対数はちょうどこの逆の操作である。たとえば、"k" についての方程式（合同式） 3 ≡ 13 (mod 17) を考えると、"k" = 4 がこの方程式の解になっていることはすでに述べたとおりであるが、これは唯一の解ではない。実際、3 ≡ 1 (mod 17) であるから、"n" を整数として 3 ≡ 13 × 1 ≡ 13 (mod 17) であり、この方程式は 4 + 16 "n" の形の解を無数にもつ。さらに、3 ≡ 1 (mod 17) を満たす最小の正整数 "m" は 16 である（すなわち、16 は (Z/17Z) における 3 の位数である）から、方程式の解はこの形のものに限られる。以上のことから、この方程式の解は "k" ≡ 4 (mod 16) で表せる。もう少し一般に、"n" を整数として既約剰余類群 "G" = (Z/"n"Z) が巡回群であると仮定する（そのような "n" は 2, 4 および素数冪 "q" と 2 "q" の形に書けるものに限られる）と、群 "G" の位数は φ("n") だから位数 φ("n") となる元（"n" を法とする原始根 と呼ばれる）"b" が存在して、"G" の各元 "a" に対して "b" ≡ "a" となるような "k" は φ("n") を法として一意に定まる（このときの離散対数はしばしば指数 と呼ばれる）。先の例では φ(17) = 16 で "b" = 3 が (Z/17Z) を生成する位数 16 の元であり、"a" = 13 に対して "k" mod 16 が一意に定まっていることが確認できる。一般に、"G" を位数 "n" の有限巡回群とする（群は乗法的に書かれているものとする）。"b" を "G" の生成元とすれば、"G" の任意の元 "g" は、適当な整数 "k" を用いて "g" = "b" の形に書ける。さらに、"g" を表現する二つの整数 "k

出典:wikipedia