アルゴリズム論特論（塩田）第10回 (3) 拡張フェルマ法
拡張フェルマ法
フェルマ法は $p \mbox{ ≒ } q$ のときに有効な素因数分解法でした。
これを拡張して、例えば $q \mbox{ ≒ } \frac{5}{3}p$ のように、
$q$ が $p$ の単純な有理数倍に近いときに有効な素因数分解法を提案することができます。
Algorithm 8（拡張フェルマ法） ( $q \mbox{ ≒ } \frac{5}{3}p$ のときに有効な version )
- 入力：RSA modulus $n$
- 出力：$n$ の素因子 $p$, $q$
- $t=\lceil \sqrt{15n} \ \rceil$ ( $\sqrt{n}$ の切り上げ )
- $x=t^2-15n$
- $s=\lfloor \sqrt{x} \ \rfloor$ ( $\sqrt{x}$ の切り捨て )
- $s^2 \neq x$ ならば $t=t+1$ として 2° へ。
- $(t-s)$ が $3$ の倍数なら
$q=(t-s)/3$, $\ p=(t+s)/5$,
そうでなければ
$q=(t+s)/3$, $\ p=(t-s)/5$
を出力。
証明 今度は $t^2 - s^2 = 15n$ を満たす $t$, $s$ を求めていますので、
$(t-s)(t+s) = ( 3 q ) \times ( 5 p)$
であり、$t \mbox{ ≒ } \sqrt{n}$ と $3q \mbox{ ≒ } 5p$ から
$t-s \mbox{ ≒ } t+s$, $3q \mbox{ ≒ } 5p$
従って
$(t-s,t+s) = ( 3q, 5p )$ or $(5p, 3q)$
となります。(証明終)
Ex.9
p : 1024-bit
q : 1024-bit
q - (5 * p / 3) : 525-bit
n ( 2048-bit ) = 16952692284993692985505233474629517997084855158821331882501997552397722663495061401665413093414109700469766041803629671693592264408739443958936812684248435264906552801571856422815269153229578857022747232247385694443459768234492860009759223259724723071407594037193442631715415396817775635520436357270877328557733425215015707787466227584240610907289578118600666702708502212534644234100967349569684747828920301486133020280515561497977664646611748435738984139938550722814945934103901543922051342595406648535098819668544550554380102678110934099192181157726441439499835953927292513404525947646747256330166123231736515154003
p ( 1024-bit ) = 100854426630645299560723523560299679558944549103404260671551471472352614885413128672590859740154426488665351618661225827544948257552466045434885112459804403647240015057762631211384922332997660735356221802083230189032341173530787023481523525242451866450627052238209807080564430539801704340399281579541097941379
q ( 1024-bit ) = 168090711051075499267872539267166132598240915172340434452585785787254358142355214454318099566924044147775586031102043045908247095920776742391475187433108226358074243257511679313897197492949300170823576182592252005270617116193058529417245273189173513847692343375881367227642071453307205778650489313116415292657
35.012639 sec.
※ 一般に $a$, $b$ が互いに素な奇数で $q \mbox{ ≒ } \frac{a}{b}p$ のときにも、
Alg.8 の $15$ を $ab$ に換えるだけで $n$ が素因数分解できます。
もう少し工夫すれば $a$, $b$ のどちらかが偶数の場合にも拡張できます。