離散対数のソースを表示

[[代数学]]における'''離散対数'''（りさんたいすう、{{lang-en-short|discrete logarithm}}）とは、通常の[[対数]]の[[群論]]的な類似物である。
離散対数を計算する問題は[[整数の因数分解]]と以下の点が共通している： 
*両方とも難しい（[[量子コンピュータ]]以外では効率的に解く[[アルゴリズム]]が得られていない）
*片方に対するアルゴリズムはしばしばもう片方にも利用できる
*問題の困難性が[[暗号]]系の構築に利用されている

== 例 ==

離散対数を理解するのに、最も簡単なのは[[素数]] ''p'' を[[合同算術|法]]とする[[整数]]の[[合同類]]からなる集合 {1, 2, ..., ''p'' &minus; 1} に乗法を考えた{{仮リンク|既約剰余類群|en|Multiplicative group of integers modulo n}} ('''Z'''/''p'''''Z''')<sup>&times;</sup> であろう。

この群の元の ''k''-乗を知りたければ、普通の整数と看做して ''k''-乗を求め、それから ''p'' で割った剰余（余り）を求めればよい（これを'''離散冪乗'''とよぶこともある）。例えば ('''Z'''/17'''Z''')<sup>&times;</sup> を考え、この中で 3<sup>4</sup> を計算するには、まず 3<sup>4</sup> = 81 としてから、81 を 17 で割って余りの 13 を得るので、既約剰余類群 ('''Z'''/17'''Z''')<sup>&times;</sup> の中で 3<sup>4</sup> &equiv; 13 (mod 17) が成り立つ。

'''離散対数'''はちょうどこの逆の操作である。たとえば、''k'' についての方程式（合同式） 3<sup>''k''</sup> &equiv; 13 (mod 17) を考えると、''k'' = 4 がこの方程式の解になっていることはすでに述べたとおりであるが、これは唯一の解ではない。実際、3<sup>16</sup> &equiv; 1 (mod 17) であるから、''n'' を整数として 3<sup>4+16&thinsp;''n''</sup> &equiv; 13 &times; 1<sup>''n''</sup> &equiv; 13 (mod 17) であり、この方程式は 4 + 16&thinsp;''n'' の形の解を無数にもつ。さらに、3<sup>''m''</sup> &equiv; 1 (mod 17) を満たす最小の正整数 ''m'' は 16 である（すなわち、16 は ('''Z'''/17'''Z''')<sup>&times;</sup> における 3 の位数である）から、方程式の解はこの形のものに限られる。以上のことから、この方程式の解は ''k'' &equiv; 4 (mod 16) で表せる。

もう少し一般に、''n'' を整数として既約剰余類群 ''G'' = ('''Z'''/''n'''''Z''')<sup>&times;</sup> が巡回群であると仮定する（そのような ''n'' は 2, 4 および素数冪 ''q'' と 2&thinsp;''q'' の形に書けるものに限られる）と、群 ''G'' の位数は [[オイラーのφ関数|&phi;(''n'')]] だから位数 &phi;(''n'') となる元（''n'' を法とする'''原始根''' {{lang|en|(primitive root of modulo ''n'')}} と呼ばれる）''b'' が存在して、''G'' の各元 ''a'' に対して ''b''<sup>''k''</sup> &equiv; ''a'' となるような ''k'' は &phi;(''n'') を法として一意に定まる（このときの離散対数はしばしば'''[[指数 (初等整数論)|指数]]''' {{lang|en|(index)}} と呼ばれる）。先の例では &phi;(17) = 16 で ''b'' = 3 が ('''Z'''/17'''Z''')<sup>&times;</sup> を生成する位数 16 の元であり、''a'' = 13 に対して ''k'' mod 16 が一意に定まっていることが確認できる。

== 定義 ==

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

:<math>\log_b\colon G \to \mathbb{Z}/n\mathbb{Z}</math>

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

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

:<math>\log_c (g) = \log_c (b) \cdot \log_b (g)</math>

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

== アルゴリズム ==

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

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

* {{仮リンク|ベビーステップジャイアントステップ|en|Baby-step giant-step}}
* [[ポラード・ロー離散対数アルゴリズム]]
* {{仮リンク|ポラード・ラムダアルゴリズム|en|Pollard's lambda algorithm}}（「ボラード・カンガルー・アルゴリズム」とも呼ばれる）
* {{仮リンク|ポーリヒヘルマンアルゴリズム|en|Pohlig-Hellman algorithm}}
* {{仮リンク|インデックス計算アルゴリズム|en|Index calculus algorithm}}
* {{仮リンク|数体篩法|en|Number field sieve}}
* {{仮リンク|函数体篩法|en|Function field sieve}}

一方、[[量子コンピュータ]]上で動作する効率的な量子アルゴリズムが[[ピーター・ショア]]によって与えられている。<ref>{{cite journal |arxiv=quant-ph/9508027 |title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer |first=Peter |last=Shor |journal=SIAM Journal on Computing |volume=26 |issue=5 |year=1997 |pages=1484–1509 |doi=10.1137/s0097539795293172 | mr=1471990}}</ref>

== 暗号への応用 ==

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

離散対数による暗号システムでは普通は群 <math>G</math> として巡回群 <math>\mathbb Z_{p}^\times</math> を採る。
{{Main|ElGamal暗号|ディフィー・ヘルマン鍵共有|電子署名}}

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

2012年6月18日、[[富士通]]、情報通信研究機構（[[NICT]]）、[[九州大学]]は278桁（923ビット）の離散対数を用いた「ペアリング暗号」を解読したと発表した。これはIntel Xeonプロセッサー252コアを148日稼働した結果である。スーパーコンピュータ「京」で換算すると13.6分に相当し、十分解読可能といえる（3357ビットならば将来にわたり十分安全といえるとしている。）<ref>[https://www.nict.go.jp/press/2012/06/18/material.pdf 「次世代暗号の解読で世界記録を達成」 ][[情報通信研究機構]]・プレスリリース 2012年6月18日</ref>。

== 参考文献 ==
* [[Richard Crandall]]; [[Carl Pomerance]]. Chapter 5, ''Prime Numbers: A computational perspective'', 2nd ed., Springer.
* Douglas R. Stinson. ''Cryptography: Theory and Practice'', CRC Press, 2002.

==引用==
<references/>

{{DEFAULTSORT:りさんたいすう}}
[[Category:暗号技術]]
[[Category:群論]]
[[Category:数学に関する記事]]
[[Category:対数]]
[[Category:有限体]]