📂整数論

ポラードのp-1素因数分解アルゴリズムの証明

アルゴリズム ¹

準素数 $N$ が与えられたとする。$p$ が スムーズ 素数であれば、$N$ の素因数分解 $N = pq$ は次のように求めることができる。

---

ステップ 1.

$a := 2$ と $L := 1$ を設定する。

---

ステップ 2.

$d := \gcd ( a^{L} - 1 , N )$ を計算する。

---

ステップ 3.

$1< d < N$ ならば、$N$ の 約数 $d = p$ を見つけたことになり、終了する。それ以外の場合は、$L := (L+1)!$ のように更新する。$L$ があまりに大きくなった場合は、$L := 1$ に戻り、$a : = a+ 1$ のように更新する。その後、ステップ 2 に戻る。

説明

ポラードの $p-1$ 素因数分解アルゴリズムは、ポリグ-ヘルマンアルゴリズムのように スムーズ素数 の弱点を利用する。一つの素数が弱点になって、素因数分解問題が簡単に解けてしまう。この攻撃方法のため、素因数分解問題の難しさを利用した暗号システムは、秘密鍵としてスムーズ素数を使用できなくなる。

原則として、ステップ 1のように $a=2$ から始める必要も、ステップ 2のように $L = n!$ を使用する必要もない。ただ、$p$ がスムーズであれば、$d := \gcd ( a^{L} - 1 , N )$ を成功させる確率が高いため、そのように使用されるだけだ。

証明

$$(p-1) \mid L \\ (q-1) \nmid L$$ $p$ は スムーズ であるから、$L = n!$ に対して上記の条件を満たしやすいと仮定する。これは、ある $i,j \in \mathbb{Z}$ と $k \in \mathbb{N}$ に対して、次のことが成立するということである。 $$\begin{align*} L =& i ( p -1 ) \\ L =& j ( q -1 ) + k \end{align*}$$

フェルマーの小定理: 素数 $p$ と $p$ と互いに素な整数 $a$ に対して、$a^{p-1} \equiv 1 \pmod{p}$

$\pmod{p}$ では $$\begin{align*} a^{L} & \equiv a^{( p - 1 ) i } \\ & \equiv 1^{i} \\ & \equiv 1 \pmod{p} \end{align*}$$ $\pmod{q}$ では $$\begin{align*} a^{L} & \equiv a^{( q - 1 ) j + k } \\ & \equiv 1^{j} a^{k} \\ & \equiv a^{k} \pmod{q} \end{align*}$$ ここで、$k \ne 0$ より、通常の場合は $a^{k} \ne 1 \pmod{q}$ である可能性が高い。これは、再び言えば $$p \mid a^{L} -1$$

$$q \nmid a^{L} -1$$ これは、$p$ が $a^{L} -1$ の 約数 であることを意味しており、$p$ が $N$ の 約数 でもあるため、二つの数の最大公約数を計算すると $$p = \gcd \left( a^{L} - 1 , N \right)$$

■

関連項目

• 素因数分解

素因数分解問題の難しさを利用したセキュリティアルゴリズム

• RSA 公開鍵暗号システム
• ゴールドワッサー-ミカリ確率鍵暗号システム

素因数分解問題に対する攻撃アルゴリズム

• ポラードの p-1素因数分解アルゴリズム
• 準素数の素因数分解問題が容易に解ける条件