離散対数 - Wikipedia

代数学における離散対数（りさんたいすう、英: discrete logarithm）とは、通常の対数の群論的な類似物である。 離散対数を計算する問題は整数の因数分解と以下の点が共通している： 両方とも難しい（量子コンピュータ以外では効率的に解くアルゴリズムが得られていない） 片方に対するアルゴリズムはしばしばもう片方にも利用できる 問題の困難性が暗号系の構築に利用されている 例[編集] 離散対数を理解するのに、最も簡単なのは素数 p を法とする整数の合同類からなる集合 {1, 2, ..., p − 1} に乗法を考えた既約剰余類群（英語版） (Z/pZ)× であろう。 この群の元の k-乗を知りたければ、普通の整数と看做して k-乗を求め、それから p で割った剰余（余り）を求めればよい（これを離散冪乗とよぶこともある）。例えば (Z/17Z)× を考え、この中で 34 を計算するには、