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

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

$n, m, N, k, a_{l}, b_{l}, c_{l}, \dots, X_{l}, n_{o}, k, l, o \in N$ (Xは任意の記号)
素因数を求める数が $m$ 、初項は $f (m)$ とする。
$f (m) = a_{n_{0}} (m + 1)^{n_{0}} + a_{n_{0} - 1} (m + 1)^{n_{0} - 1} + \dots + a_{1} (m + 1) - a_{0} (a_{0} = b_{0} = c_{0} = \dots 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} + \dots + b_{1} f (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}} + \dots + X_{1} f (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 ≧ 1$ ）と $N$ のgcdを求める。

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

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

たまねぎくんの解説

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

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

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

追記 2024/1/8