書記が数学やるだけ#893 素因数分解アルゴリズムの例-2

今回はFermat法・2次篩法・数体篩法を見ていく。

問題

説明

Fermat法は，任意の奇数 N を N = x^2 - y^2 = (x-y)(x+y) の形に表すことを利用したアルゴリズムで，因数が近い場合に有効である。

二次篩法（Quadratic Sieve, QS）では，多くの x に対し x^2 mod N を計算し，素因数分解が「因子基底」と呼ばれる小素数だけで表せる場合を集める。その後，線形代数を用いて合同式

$$x^2 \equiv y^2 \pmod N$$

を構成し、N の因数を得る。

数体篩法（General Number Field Sieve, GNFS）では，多項式と代数的数体を利用して「滑らかな数」を収集し，QS と同様に線形代数により合同式を作る。この手法は，現在知られている中で最速の古典的な一般整数分解アルゴリズムであり，計算量は準指数時間である。

解答

Fermat法は、合成数 N を平方数の差として表すことに基づく因数分解法である。すなわちN=x2−y2=(x−y)(x+y)とおくことで、N を二つの因数の積に分解できる。このとき、x=p+q/2 , y=q−p/2  とすると、p と q は N の素因数である。特に p と q の差が小さい場合（p≈q），x は N の近傍に位置するため、探索はすぐに終了する。このため Fermat 法は、互いに近い2つの素数の積に対して有効である。しかし、素因数の差が大きい場合には探索が長引き、効率が著しく低下する。

N = 11413 を 2次篩法で分解する。まず N ≈106.85 なので ⌈N ⌉=107 とし，Q(x)=(x+107)2−11413を定義する。ここで得られる値 Q(x) を小さな素数集合 B={2,3,5,7} で割り切れるかを調べ，B-smooth数を集める。十分な数のBスムーズ数が得られると，それらの積が平方数になる関係を利用して合同式a^2≡b^2(modN)を導き，最終的に gcd(a−b,N) から非自明な因数を得る。

計算量を計算すると，100桁程度までの中規模整数には2次篩法が有効であり，100桁以上の大規模整数には数体篩法が有効であると言える。

実際には，数体篩法は 200桁前後までの整数分解に実際に使えるが，RSA-1024やRSA-2048のような実用暗号には現状では通用しない。ただし量子計算機が登場すれば，RSA暗号全般が破られる可能性がある。

本記事のもくじはこちら：