📂整数論

離散対数

定義 ¹

素数 $p$ について、ガロア体 $\mathbb{F}_{p} := \mathbb{Z} / p \mathbb{Z}$ の恒等元が $0$ だとしよう。

$\mathbb{F}_{p}$ の原始根 $g \ne 0$ に関して、巡回群 $\mathbb{F}_{p} ^{ \ast } := \mathbb{F}_{p} \setminus \left\{ 0 \right\} = \left< g \right>$ 上で定義された関数 $\log_{g} : \mathbb{F}_{p}^{ \ast } \to \mathbb{Z} / (p-1) \mathbb{Z}$ が次の条件を満たすとき、離散対数^{discrete Logarithm}と呼ぶ。 $$ g^{ \log_{g} (h) } \equiv h \pmod{p} $$

説明

$\mathbb{F}_{p} ^{ \ast }$ の存在は原始根定理によって保証される。

実際、離散対数はすべての $a,b \in \mathbb{F}_{p}^{ \ast }$ に対して $\log_{g} (ab) = \log_{g} (a) + \log_{g} (b)$ であるため、同型となる。

通常の対数と異なり、暗号学での対数はその計算の困難さのために有用であるが、与えられた $k$ に対して $$ g^{k} \equiv x \pmod{p} $$ を満たす $x$ を見つけることは連続累乗法を使用すればそれほど難しくないが、与えられた $h$ に対して $$ g^{x} \equiv h \pmod{p} $$ を満たす $x$ を見つけることは難しい。これを離散対数問題^{discrete Logarithm Problem}と呼び、暗号の必要不可欠な特性を持ち、暗号学全般で広く使用されている。

一方、離散対数問題は群 $\left( G , \ast\ \right)$ 上で一般化することもできる。問題自体は依然として $$ g \ast\ \cdots \ast\ g = h $$ を満たすために、$g \ast\ g$ を何回見つけなければならないかを問うだけである。これは、暗号学の限界が整数論でないことを意味する。

同時に見る

• 離散対数問題

離散対数問題の難しさを利用した暗号アルゴリズム

• ディフィー・ヘルマン鍵交換アルゴリズム
• エルガマル公開鍵暗号システム

離散対数問題に対する攻撃アルゴリズム

• シャンクスのアルゴリズム
• ポラードのロー・アルゴリズム
• 離散対数問題が容易に解ける条件