流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【素因数分解】ぼくの考えたアルゴリズム【RSAに挑む】

オリジナルプチ研究数学素因数分解

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

2つの素数の積からなる合成数の素因数分解

2つの素数 $p,q$ の積からなる合成数 $N=pq$ を考える。

ここで、 $p$ または $q$ の片方のみを素因数に持つ自然数 $X$ を用意すると、

$\gcd(N,X)$ をユークリッドの互除法で計算すれば、求める素因数の片方が分かるので、素因数分解できる。

ここで、自然数 $X$ をいかにして用意するかが問題となる。

素数階乗冪多項式

$P$ を素数階乗とする。このとき、

$P=p_n \#=2 \times 3 \times 5 \times \cdots \times p_n$

とおき、自然数 $1 \le a \le p_n$ に対して、多項式

$f^{(P)}(a)=P^P-a^P$

を考える。

$X=f^{(P)}(a)$ とおいて、 $\gcd(N,X)$ が $1$ でも $N$ でもない自然数になれば、それが $N$ の素因数となる。これが見つかるかどうかは、確率次第だと思うので、成功確率は今のところ不明である。

計算量

ユークリッドの互除法を行う回数は、 $p_n$ 回である。よって、計算量は、

$O(p_n \log N)$ である。

事前に用意する素数の個数nが多ければ多い程、素因数分解の成功確率は上がると期待されるが、計算量がその代わりに増加するので、適切な素数の個数を見つけなければいけない。

例

素数を１つ取って、 $n=1,p_1=2$ とする。

$f^{(2)}(1)=3$

この場合、9までの素因数分解が可能である。

素数を２つ取って、 $n=2,p_2=3$ とする。

$f^{(6)}(1)=5\times 7\times 31\times 41$

$f^{(6)}(2)=2^9 \times 7 \times 13$

$f^{(6)}(3)=3^8\times 7$

この場合、素因数に11を含む場合を除く、169までの素因数分解が可能である。

素数を3つ取って、 $n=3,p_2=5$ とする。

$f^{(30)}(1)=7 \times 11\times 13 \times 19\times29 \times 31 \times 67 \times \cdots$

$f^{(30)}(2)=2^6 \times 7\times 43 \times \cdots$

$f^{(30)}(3)=3 \times 7\times 13^2 \times 41 \times \cdots$

$f^{(30)}(4)=2^{12} \times 7 \times 13\times 17 \times \cdots$

$f^{(30)}(5)=5^6 \times 7 \times 31 \times 79 \times \cdots$

この場合、素因数に23を含む場合を除く、1296までの素因数分解が可能である。