離散対数

離散対数とは

代数学における離散対数（discrete logarithm）は、通常の対数の群論的な類似概念です。これは、特に暗号技術において重要な役割を果たしています。離散対数の計算は、整数の因数分解と同様に、古典的なコンピュータでは効率的なアルゴリズムが知られていない難しい問題であり、その困難性が暗号システムの安全性に利用されています。

離散対数の基本概念

離散対数を理解する上で、最も簡単な例は素数 p を法とする整数の合同類からなる集合 \{1, 2, ..., p − 1\} に乗法を考えた既約剰余類群 (Z/pZ)× です。この群において、ある元の k-乗を計算するには、通常の整数として k-乗を求めた後、その結果を p で割った余りを求めます。これを離散冪乗と呼びます。

例えば、(Z/17Z)× において 3^4 を計算する場合、まず 3^4 = 81 とし、81 を 17 で割った余りである 13 を得ます。したがって、(Z/17Z)× の中で 3^4 ≡ 13 (mod 17) が成り立ちます。

離散対数はこの逆演算です。つまり、3^k ≡ 13 (mod 17) を満たす k を求める問題が離散対数問題です。この例では k = 4 が解の一つですが、実際には 3^16 ≡ 1 (mod 17) であるため、3^4+16n ≡ 13 (mod 17) となる n を整数として、解は無限に存在します。

より一般的に、既約剰余類群 G = (Z/nZ)× が巡回群である場合、群の位数を φ(n) とすると、G の各元 a に対して、b^k ≡ a となる k が φ(n) を法として一意に定まります。この k が離散対数です。

離散対数の定義

一般に、G を位数 n の有限巡回群とし、b を G の生成元とします。このとき、G の任意の元 g は、適当な整数 k を用いて g = b^k と表現できます。この k は n を法として一意に定まります。したがって、g に n を法とする k の合同類を対応させることで、以下の写像を定義できます。

log_b : G → Z/nZ

この写像は群同型写像であり、b を底とする離散対数と呼ばれます。

また、通常の対数と同様に、底の変換公式も存在し、別の生成元 c に対して、以下の式が成り立ちます。

log_c(g) = log_c(b) ⋅ log_b(g)

離散対数の計算アルゴリズム

群 G における離散対数 log_b(g) を計算する効率的なアルゴリズムは知られていません。ナイーブな方法としては、b の1乗、2乗、3乗、...を順に計算し、求める g が得られるまで続ける方法があります。

しかし、このアルゴリズムは G の位数に対して線形な時間、つまり要素の桁数に対して指数的な時間を要するため、巨大な G に対しては実用的ではありません。

より高度なアルゴリズムも存在しますが、これらも多項式時間で計算が終わるわけではありません。代表的なアルゴリズムとしては以下のようなものがあります。

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

これらのアルゴリズムは、整数の因数分解アルゴリズムと類似したアイデアに基づいています。

一方、量子コンピュータ上では、ピーター・ショアによって効率的な量子アルゴリズムが発見されており、将来的に離散対数の計算が容易になる可能性もあります。

暗号への応用

離散対数の計算が難しいという性質は、現代の暗号システムにおいて重要な役割を果たしています。この非対称性、すなわち離散対数の計算が難しくても、逆演算である離散冪乗が容易であるという性質は、整数の因数分解と乗算の関係に似ています。

具体的には、離散対数を用いた暗号システムでは、通常、群 G として巡回群 Z_p^× を用います。また、最近の暗号システムでは、有限体上の楕円曲線の周回部分群における離散対数も利用されています。

近年の事例

2012年、富士通、情報通信研究機構（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.

もう一度検索