離散対数問題

デジタル大辞泉

りさんたいすう‐もんだい【離散対数問題】

読み方：りさんたいすうもんだい

素数pと定数aが与えられ、整数yを素数pでa^xを除したときの剰余とするとき、yについて整数解xを求める問題。

[補説] xからyを計算することは容易だが、pが大きな数である場合、yからxを計算することは非常に困難であり、総当たりで計算しても膨大な時間がかかってしまう。解を得ることが困難な数学的性質から、エルガマル暗号や楕円曲線暗号などの基本原理として、公開鍵暗号に安全性を保証している。

ウィキペディア

離散対数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 06:40 UTC 版)

代数学における離散対数（りさんたいすう、英: 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 の合同類を対応させることにより

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

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

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

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

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

アルゴリズム

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

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

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

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

暗号への応用

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

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

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

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

参考文献

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