アルゴリズム論特論(塩田)第10回 (1) フェルマ法

フェルマ法

 今日は $n=p \times q$ は RSA modulus を表すものとします。 すなわち、$n$ は大きな 2 つの異なる素数 $p$, $q$ ( $p \lt q$ ) を掛けた合成数とします。
Lemma 1 $n$ を知っている者にとって、$p$, $q$ を知ることと、
$n = t^2 - s^2$
を満たす正整数 ( $0 \lt s \lt t \lt \frac{n}{2}$ ) を知ることは同値である。
証明 $\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}$ の切り上げから探索し始めればよく、 次のようなアルゴリズムが考えられます。
Algorithm 2(フェルマ法) 
  • 入力:RSA modulus $n$
  • 出力:$n$ の素因子 $p$, $q$
  1. $t=\lceil \sqrt{n} \ \rceil$   ( $\sqrt{n}$ の切り上げ )
  2. $x=t^2-n$
  3. $s=\lfloor \sqrt{x} \ \rfloor$   ( $\sqrt{x}$ の切り捨て )
  4. $s^2 \neq x$  ならば  $t=t+1$  として 2° へ。
  5. $p=t-s$, $\ q=t+s$ を出力。
やってみよう $n=2701$ に対してフェルマ法を実行してみましょう。
 $p\mbox{ ≒ }q$ であれば $\displaystyle{s=\frac{q-p}{2}}$ が小さいので
$\displaystyle{t^2 = n + s^2 \mbox{ ≒ } n}$
となり、$t$ はすみやかに見つかります。
Prop.3 $\require{color}\textcolor{red}{p\mbox{ ≒ }q}$ のとき Alg.2高速に $n$ を素因数分解する。

実行例

 次の例では、1024ビット中、上位504ビットが一致するような 2 つの素数を $p$, $q$ として選んでいます。 フェルマ法を使えば RSA modulus はわずか 9000 個弱の $t$ を検索するだけで素因数分解されています。
Ex.4 
素数 p, q のビット数を設定してください。
1024
p と q の差のビット数を設定してください。
520
n = 14149196112247687514027611690732581057503952470709895321388545930824272461201638826590827469315424651523954054382523215566934126979677087970726960197577030999103905968384920488016638041291848046473345848556962223449508878431484461476374272525529947067142190420240413070585979486301904692717454949880813932823442524095614486334454675925145812635243647435580822261952074675533389645899770658475187265610495308115447728317882907660075844673403666542377724402705012882290844170647248595447494740840022084750323565027630771483439556225960734255218999654870501172885973827476094508630332215229005524065867117983516852518541 ( 2047 ビット )
Fermat 法 開始
p = 118950393493454604519592318493413137610691467733052763094120425109015480242836760706582304494291938693713118619402131067177626273768646807372589711103532727492278092426469001325987271423168242480212037196980248091240710081028224993861297478298291257999087827691720198271118490686182430877712824180627090189037
q = 118950393493454604519592318493413137610691467733052763094120425109015480242836760706582304494291938693713118619402131067177626273768646807372589711103535593528215019842954436134049006570412739240738283604621704252231626584784795519989965761597769923483650893988583717495699602504463088564579506924418561871393
検算 :
p * q = 14149196112247687514027611690732581057503952470709895321388545930824272461201638826590827469315424651523954054382523215566934126979677087970726960197577030999103905968384920488016638041291848046473345848556962223449508878431484461476374272525529947067142190420240413070585979486301904692717454949880813932823442524095614486334454675925145812635243647435580822261952074675533389645899770658475187265610495308115447728317882907660075844673403666542377724402705012882290844170647248595447494740840022084750323565027630771483439556225960734255218999654870501172885973827476094508630332215229005524065867117983516852518541
ステップ数 : 8631
計算時間 = 30.10787606239319 sec.