離散対数

離散対数の最新ニュースをまとめて検索！

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

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

[編集] 例

離散対数の簡単な例は、素数 p を法とする整数の乗法群 で考えるとよい。 これは1から p − 1 までの整数の集合であり、 p を法とする乗算に対して群をなしている。

この群においてある元の k 乗を知りたければ、 普通の整数として k 乗した後に p で割ったときの剰余（余り）を取ればよい。 例えば を考える。 この群において 3⁴ を求めるには、普通の整数として3⁴ = 81を計算し、 81を17で割って、余りの13を答えとする。 なお3を掛ける毎に剰余を計算してもよい。

この逆操作が離散対数である。 すなわち「 のとき、この式を満たす k はいくつか？」という問である。 これには実際には無限個の解があるが（解に17の整数倍を足してよい不定性があるため）、 普通はそのうちで最小の非負整数を選ぶ。 すなわち k = 4 である。

[編集] 定義

一般に、G を位数 n の巡回群とする（群の演算は積のように書き表す）。 b を G の生成元とする。 このとき G の任意の元 g は、 適当な整数 k を用いて g = b^k の形に書ける。 さらに同一の g をそのように表現する任意の二つの整数は n を法として合同である。 よって、各 g に k の n を法とする同値類を対応付けることで、 次のような関数を定義できる：

ここで は整数環 の n を法とした合同関係による商環である。 この関数は群同型写像であり、底を b としたときの離散対数と呼ぶ。

通常の対数と同様に底の変換公式が成立する：

ここで c は G の別の生成元である。

[編集] アルゴリズム

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

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

• en:Baby-step giant-step (Also known as 'Little-Step Big-Step')
• en:Pollard's rho algorithm for logarithms
• en:Pollard's lambda algorithm (aka en:Pollard's kangaroo algorithm)
• en:Pohlig-Hellman algorithm
• en:Index calculus algorithm
• en:Number field sieve
• en:Function field sieve

[編集] 暗号への応用

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

離散対数による暗号システムでは普通は群 G として巡回群 を採る。

詳細は「ElGamal暗号」、「ディフィー・へルマン鍵共有」、「電子署名」をそれぞれ参照

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

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

この項目「離散対数」は、数学に関連した書きかけの項目です。加筆・訂正などをして下さる協力者を求めています。（P:数学／PJ:数学）