かわぐちさんの素因数発見アルゴリズムと、合成数の発見方法（素数は作れないが、間接的に作れる）

かわぐちさんの素因数発見アルゴリズム

$n, m, N, k, a_l, b_l, c_l,\cdots,X_l, n_o, k, l, o∈\mathbb{N}$(Xは任意の記号)
素因数を求める数が$m$、初項は$f(m)$とする。
$f(m)=a_{n_0}(m+1)^{n_0}+a_{n_0-1}(m+1)^{n_0-1}+\dotsb +a_1(m+1)-a_0(a_0=b_0=c_0=\dotsb X_0=\sum{a_{n_k}-1}$
Xは任意の記号でaから数えてk-1番目)

$f(m+1)=b_{n_1}f(m)^{n_1}+b_{n_1-1}f(m)^{n_1-1}+\dotsb+b_1f(m)-b_0$
$f(m+k)=X_{n_k}f(m+k-1)^{n_{k-1}}+X_{n_k-1}f(m+k-1)^{n_{k-2}}+\dotsb +X_1f(m+k-1)-X_0$
数列$X_m, n_k$を総当りにする。
$n_k$（$k$は任意の0を含む自然数）は非常に大きな値にする。
素数の無限積の途中までの数をNとする。
mod Nでmをどんどん大きくし、f(m) mod Nを求める。
全ての項同士の差Zを求め、NとZのgcdを求めると、それがmの約数である。
$G_k=f(x)-f(y)$（$x,y$は自然数かつ$x>y,m\geqq 1$）と$N$のgcdを求める。

こうぼくん「……？？？」
かわぐちさん「分かんないね」
こうぼくん「うん」
（こうぼくんが困ってしまった）

たまねぎくん「解説してあげるよ」

たまねぎくんの解説

なんでこんな風に難しくなってしまったかというと、実際にこのアルゴリズムを用いる際に、可能な限り自由に計算ができるように、一般化し過ぎたからです。
要するに、素因数を求める数が$x$、
$x$の倍数を$Px, Qx, Rx$とした時に
$a(x+1)^{10}-a+1=Px+1$
$b(x+1)^{20}-b+1=Qx+1$
$c(Px+1)^{30}-c+1=Rx+1$
という風になるので、
$f(x)=Px+1$
$f_2(x)=Qx+1$
とした時に、
$f_2(x)-f(x)=(Q-P)x$
となり、xの倍数ができます。
全ての数の共通の素因数は、非常に高い確率でxの素因数です。
■

こうぼくん「なるほど」
かわぐちさん「分かった」
こうぼくん「よかった」

初学者の為の、mod Nでも計算できる理由
$24637\equiv4637\pmod {5000}$
この余りの4637と5000の共通の素因数は、24637の素因数です。
$76000\equiv1000\pmod {5000}$
$1000$と$5000$の共通の素因数は、$76000$の素因数です。
$\begin{eqnarray} &a&=5000n+1000\\ &&=1000*(5n+1) \end{eqnarray}$
一般化すると、
$\begin{eqnarray} &a&=Nn+r\\ &&=r*((N/r)n+1) \end{eqnarray}$
従って、$N=2*3*5*7*11*\dotsm $の場合、Nが素数の積なので、Nの素因数の素数とrの共通の素因数は、aの素因数です。

追記 2024/1/8