アルゴリズム論特論(塩田)第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$
- $t=\lceil \sqrt{n} \ \rceil$ ( $\sqrt{n}$ の切り上げ )
- $x=t^2-n$
- $s=\lfloor \sqrt{x} \ \rfloor$ ( $\sqrt{x}$ の切り捨て )
- $s^2 \neq x$ ならば $t=t+1$ として 2° へ。
- $p=t-s$, $\ q=t+s$ を出力。
やってみよう $n=2701$ に対してフェルマ法を実行してみましょう。
$\sqrt{2701}=51.971\cdots$ より $t$ の初期値は $52$ で
$t = 52$ のとき $x = 52^2 - 2701 = 3,\phantom{00}\quad s = 1,\phantom{0}\quad x \neq s^2$
$t = 53$ のとき $x = 53^2 - 2701 = 108,\quad s = 10,\quad x \neq s^2$
$t = 54$ のとき $x = 54^2 - 2701 = 215,\quad s = 14,\quad x \neq s^2$
$t = 55$ のとき $x = 55^2 - 2701 = 324,\quad s = 18,\quad x = s^2$
よって
$p = t - s = 37$, $q = t + s = 73$
$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.