|
代数学における離散対数（りさんたいすう、）とは、通常の対数の群論的な類似物である。 離散対数を計算する問題は整数の因数分解(:en:integer factorization)と以下の点が共通している： *両方とも難しい（量子コンピュータ以外では効率的に解くアルゴリズムが得られていない） *片方に対するアルゴリズムはしばしばもう片方にも利用できる *問題の困難性が暗号系の構築に利用されている == 例 == 離散対数を理解するのに、最も簡単なのは素数 ''p'' を法とする整数の合同類からなる集合 に乗法を考えた既約剰余類群 (Z/''p''Z)× であろう。 この群の元の ''k''-乗を知りたければ、普通の整数と看做して ''k''-乗を求め、それから ''p'' で割った剰余（余り）を求めればよい（これを離散冪乗とよぶこともある）。 例えば (Z/17Z)× を考え、この中で 34 を計算するには、 まず 34 = 81 としてから、81 を 17 で割って余りの 13 を得るので、既約剰余類群 (Z/17Z)× の中で 34 ≡ 13 (mod 17) が成り立つ。 離散対数はちょうどこの逆の操作である。たとえば、''k'' についての方程式（合同式） 3''k'' ≡ 13 (mod 17) を考えると、''k'' = 4 がこの方程式の解になっていることはすでに述べたとおりであるが、これは唯一の解ではない。実際、316 ≡ 1 (mod 17) であるから、''n'' を整数として 34+16 ''n'' ≡ 13 × 1''n'' ≡ 13 (mod 17) であり、この方程式は 4 + 16 ''n'' の形の解を無数にもつ。さらに、3''m'' ≡ 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''''k'' ≡ ''a'' となるような ''k'' は φ(''n'') を法として一意に定まる（このときの離散対数はしばしば指数 と呼ばれる）。先の例では φ(17) = 16 で ''b'' = 3 が (Z/17Z)× を生成する位数 16 の元であり、''a'' = 13 に対して ''k'' mod 16 が一意に定まっていることが確認できる。 この群の元の ''k''-乗を知りたければ、普通の整数と看做して ''k''-乗を求め、それから ''p'' で割った剰余（余り）を求めればよい（これを離散冪乗とよぶこともある）。 例えば (Z/17Z)× を考え、この中で 34 を計算するには、 まず 34 = 81 としてから、81 を 17 で割って余りの 13 を得るので、既約剰余類群 (Z/17Z)× の中で 34 ≡ 13 (mod 17) が成り立つ。 離散対数はちょうどこの逆の操作である。たとえば、''k'' についての方程式（合同式） 3''k'' ≡ 13 (mod 17) を考えると、''k'' = 4 がこの方程式の解になっていることはすでに述べたとおりであるが、これは唯一の解ではない。実際、316 ≡ 1 (mod 17) であるから、''n'' を整数として 34+16 ''n'' ≡ 13 × 1''n'' ≡ 13 (mod 17) であり、この方程式は 4 + 16 ''n'' の形の解を無数にもつ。さらに、3''m'' ≡ 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''''k'' ≡ ''a'' となるような ''k'' は φ(''n'') を法として一意に定まる（このときの離散対数はしばしば指数 と呼ばれる）。先の例では φ(17) = 16 で ''b'' = 3 が (Z/17Z)× を生成する位数 16 の元であり、''a'' = 13 に対して ''k'' mod 16 が一意に定まっていることが確認できる。 Z)× を生成する位数 16 の元であり、''a'' = 13 に対して ''k'' mod 16 が一意に定まっていることが確認できる。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「離散対数」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Discrete logarithm 」があります。 スポンサード リンク
|