離散対数
離散対数を理解するのに、最も簡単なのは素数 p を法とする整数の合同類からなる集合 {1, 2, ..., p − 1} に乗法を考えた既約剰余類群(英語版) (Z/pZ) であろう。
この群の元の 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 の形の解を無数にもつ。