戻る / 次へ

フェルマ法

　今日は $n=p \times q$ は RSA modulus を表すものとします。 すなわち、$n$ は大きな 2 つの異なる素数 $p$, $q$ ( $p \lt q$ ) を掛けた合成数とします。 証明　$\Rightarrow$ )　$p$, $q$ は奇素数ですから  $\displaystyle{t=\frac{p+q}{2}}$,  $\displaystyle{s=\frac{q-p}{2}}$  は正整数であり、 $t^2-s^2=(t-s)(t+s)=p \times q = n$. となります。また $p \lt q$ から $\displaystyle{0 \lt s \lt t=\frac{p+q}{2}} \lt q = \frac{n}{p} \lt \frac{n}{2}$. $\Leftarrow$ )　$n=t^2-s^2$,  $0 \lt s \lt t \lt \frac{n}{2}$ であれば $n=(t-s)(t+s)$,   $ 0 \lt t-s \lt t+s \lt n$ となり、$t+s$ は $n$ の大きい方の素因数、すなわち $t-s =p$,   $t+s=q$ となります。(証明終)

　相加・相乗平均の関係から $\displaystyle{t=\frac{p+q}{2} \geqq \sqrt{\,p\,q} = \sqrt{n}}$ ですから、$t$ は $\sqrt{n}$ の切り上げから探索し始めればよく、 次のようなアルゴリズムが考えられます。 　$p\mbox{ ≒ }q$ であれば $\displaystyle{s=\frac{q-p}{2}}$ が小さいので $\displaystyle{t^2 = n + s^2 \mbox{ ≒ } n}$ となり、$t$ はすみやかに見つかります。

実行例

　次の例では、1024ビット中、上位504ビットが一致するような 2 つの素数を $p$, $q$ として選んでいます。 フェルマ法を使えば RSA modulus はわずか 9000 個弱の $t$ を検索するだけで素因数分解されています。

戻る / 次へ