離散対数

代数学における離散対数（りさんたいすう、英: discrete logarithm）とは、通常の対数の群論的な類似物である。 離散対数を計算する問題は整数の因数分解と以下の点が共通している：

• 両方とも難しい（量子コンピュータ以外では効率的に解くアルゴリズムが得られていない）
• 片方に対するアルゴリズムはしばしばもう片方にも利用できる
• 問題の困難性が暗号系の構築に利用されている

例

離散対数を理解するのに、最も簡単なのは素数 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^k ≡ 13 (mod 17) を考えると、k = 4 がこの方程式の解になっていることはすでに述べたとおりであるが、これは唯一の解ではない。実際、3¹⁶ ≡ 1 (mod 17) であるから、n を整数として 3^4+16 n ≡ 13 × 1ⁿ ≡ 13 (mod 17) であり、この方程式は 4 + 16 n の形の解を無数にもつ。さらに、3^m ≡ 1 (mod 17) を満たす最小の正整数 m は 16 である（すなわち、16 は (Z/17Z)^× における 3 の位数である）から、方程式の解はこの形のものに限られる。以上のことから、この方程式の解は k ≡ 4 (mod 16) で表せる。

もう少し一般に、n を整数として既約剰余類群 G = (Z/nZ)^× が巡回群であると仮定する（そのような n は 2, 4 および素数冪 q と 2 q の形に書けるものに限られる）と、群 G の位数は φ(n) だから位数 φ(n) となる元（n を法とする原始根 (primitive root of modulo n) と呼ばれる）b が存在して、G の各元 a に対して b^k ≡ a となるような k は φ(n) を法として一意に定まる（このときの離散対数はしばしば指数 (index) と呼ばれる）。先の例では φ(17) = 16 で b = 3 が (Z/17Z)^× を生成する位数 16 の元であり、a = 13 に対して k mod 16 が一意に定まっていることが確認できる。

定義

一般に、G を位数 n の有限巡回群とする（群は乗法的に書かれているものとする）。b を G の生成元とすれば、G の任意の元 g は、適当な整数 k を用いて g = b^k の形に書ける。さらに、g を表現する二つの整数 k₁, k₂ は必ず n を法として合同である。したがって、g に n を法とする k の合同類を対応させることにより

${\displaystyle \log _{b}\colon G\to \mathbb {Z} /n\mathbb {Z} }$

なる函数を定義することができる。ここで Z/nZ は n を法とする整数の剰余類環である。この関数は群同型写像であり、b を底とする離散対数と呼ばれる。

通常の対数と同様の底の変換公式が、c を G の別の生成元として

${\displaystyle \log _{c}(g)=\log _{c}(b)\cdot \log _{b}(g)}$

が成立するという意味で有効である。

アルゴリズム

群 ${\displaystyle G}$ における離散対数 ${\displaystyle \log _{b}g}$ を計算する効率の良いアルゴリズムは知られていない。 ナイーブなアルゴリズムとしては、${\displaystyle b}$ の1乗、2乗、3乗、…を順に計算し、 求める ${\displaystyle g}$ が得られるまで続ける方法がある。 このアルゴリズムは ${\displaystyle G}$ の位数について線形な、すなわち要素の桁数（特に、何ビットか）について指数的な実行時間を要し、 巨大な ${\displaystyle G}$ に対して実用的でない。

より高度なアルゴリズムも知られており、代表的なものを以下に挙げる。 整数の因数分解アルゴリズムと同様のアイディアが多い。 これらは上記のナイーブなアルゴリズムより高速であるものの、多項式時間では計算が終わらない。

• ベビーステップジャイアントステップ（英語版）
• ポラード・ロー離散対数アルゴリズム
• ポラード・ラムダアルゴリズム（英語版）（「ボラード・カンガルー・アルゴリズム」とも呼ばれる）
• ポーリヒヘルマンアルゴリズム（英語版）
• インデックス計算アルゴリズム（英語版）
• 数体篩法（英語版）
• 函数体篩法（英語版）

一方、量子コンピュータ上で動作する効率的な量子アルゴリズムがピーター・ショアによって与えられている。^[1]

暗号への応用

離散対数の計算は難しい問題（効率良いアルゴリズムが知られていない）だが、 逆の過程である離散的な冪乗は容易（→冪乗#効率的な演算法）である。 この非対称な関係は整数の因数分解と乗算との関係に似ている。 これらの非対称性は暗号システムの構築に利用される。

離散対数による暗号システムでは普通は群 ${\displaystyle G}$ として巡回群 ${\displaystyle \mathbb {Z} _{p}^{\times }}$ を採る。

→詳細は「ElGamal暗号」、「ディフィー・ヘルマン鍵共有」、および「電子署名」を参照

最近の暗号システムでは有限体上の楕円曲線の周回部分群における離散対数を利用する。

→詳細は「楕円曲線暗号」を参照

2012年6月18日、富士通、情報通信研究機構（NICT）、九州大学は278桁（923ビット）の離散対数を用いた「ペアリング暗号」を解読したと発表した。これはIntel Xeonプロセッサー252コアを148日稼働した結果である。スーパーコンピュータ「京」で換算すると13.6分に相当し、十分解読可能といえる（3357ビットならば将来にわたり十分安全といえるとしている。）^[2]。

参考文献

• Richard Crandall; Carl Pomerance. Chapter 5, Prime Numbers: A computational perspective, 2nd ed., Springer.
• Douglas R. Stinson. Cryptography: Theory and Practice, CRC Press, 2002.

引用

1. Shor, Peter (1997). “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Journal on Computing 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/s0097539795293172. MR1471990.
2. 「次世代暗号の解読で世界記録を達成」 情報通信研究機構・プレスリリース 2012年6月18日