📂整数論

離散対数問題が容易に解決される条件

要旨 ¹

グループ $G = F_{p}$ の要素 $g$ がオーダー $N$ であるとしよう。すると、離散対数問題 $g^{x} = h$ は、次の条件下では比較的簡単に解かれることになる。

• (i): $p$ がスムーズ素数である。
• (ii): $p \equiv 3 \pmod{4}$ と $a$ がモジュロ $p$ に関する二次剰余である。

証明

(i)

$p$ がスムーズな素数であれば、ポーリグ・ヘルマンアルゴリズムを利用できるため、離散対数問題は比較的簡単に解かれる。

■

(ii)

$$x^{2} \equiv a \pmod{p}$$ $a$ がモジュロ $p$ に関する二次剰余であるということは、上記合同方程式を満たす解が存在するということである。もし素数 $p$ を $4$ で割った余りが $3$ であれば、 $$b \equiv a^{(p+1)/4} \pmod{p}$$ ある $a \equiv g^{2k} \pmod{p}$ に対して、 $$\begin{align*} b^{2} \equiv & a^{{ p+1 } \over { 2 }} & \pmod{p} \\ \equiv & \left( g^{2k} \right)^{{ p+1 } \over { 2 }} & \pmod{p} \\ \equiv & g^{(p+1)k} & \pmod{p} \\ \equiv & g^{2k + (p-1)k} & \pmod{p} \\ \equiv & a \cdot \left( g^{p-1} \right)^{k} & \pmod{p} \\ \equiv & a & \pmod{p} \end{align*}$$ よって、与えられた合同方程式の解となる。この公式により、$a$ の平方根を非常に速く見つけ出すことができ、そこで離散対数問題は比較的簡単に解かれるようになる。

■

関連項目

• 離散対数問題

離散対数問題の難しさを利用したセキュリティアルゴリズム

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

離散対数問題への攻撃アルゴリズム

• シャンクスアルゴリズム
• ポーリグ・ヘルマンアルゴリズム
• 離散対数問題が簡単に解かれる条件