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

素因数分解アルゴリズムのうち，今回はPollard ρ法とPollard p-1法の原理を見ていく。

問題

説明

Pollard ρ法は，大きな整数の素因数分解に用いられるアルゴリズムであり，特に比較的サイズの小さい素因数を効率的に見つけることに適している。アルゴリズムは、ある関数 f(x) を用いて整数の列を生成し、その列の中で繰り返し出現する値（サイクル）を検出することで、対象の整数の非自明な約数を求める。

Pollard p-1 法は，特に因数 p の p-1 が小さい素因数で構成されている場合に効率的である。

解答

フロイドの循環検出法におけるサイクルの存在は、有限集合上で定義された関数の反復列に基づいて説明できる。反復列は有限集合の元しか取り得ないため、十分に多くのステップを進めると必ず同じ値が繰り返し現れる。すなわち、ある i < j に対して x_i = x_j となる。このとき、列は x_i から x_j までの部分が周期として繰り返されるサイクルを形成する。

例として N = 8051 の素因数分解を考える。ρ法では関数 f(x) = x^2 + 1 mod 8051 を用いて列 x_0, x_1, x_2, … を生成し、フロイドの検出法でサイクルを検出する。サイクルが見つかると、gcd(x_i - x_j, 8051) を計算して非自明な約数を求めることができる。

Pollard p-1 法の基本的な考え方は、フェルマーの小定理に基づき、ある整数 a に対して

$$a^{p-1} \equiv 1 \ (\mathrm{mod}\ p)$$

となる性質を利用することで、

$$\gcd(a^M - 1, N)$$

を計算し、非自明な約数を見つけることである。ここで M は p-1 の倍数となるように選ばれる数である。

整数 N = 11413 をp-1 法で素因数分解する場合、まず小さな整数 a（例えば a = 2）を選ぶ。次に、分解したい素因数 p の p-1 が小さい素数のべき乗で構成されることを利用して、上限 B を決める。具体的には、p-1 の素因数分解を想定し、すべての素数qの最大べき乗 q^k が p-1 を割り切るように M = lcm(1,2,…,B) を計算する。今回の場合はB=5でうまく計算することができる。

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