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

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

$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

ちょっと間違ってます。

素因数の積$P$で割った時の循環小数の循環する桁を見て、素数$P+1$の積で割った時の循環小数の循環する時の桁の数より循環する桁の数が小さくなっていれば、どれかの素数で割り切れています。

それ以上の上手い方法はありませんし、剰余をもう一度式に代入はできません。

合成数の発見方法

登場する数は全て非負整数。
まず
$\begin{eqnarray} &&aN+b \\ &=&(a-n)(N+m) \end{eqnarray}$
という式を作る。先にa, n, N, mを適当に決めて、bは後から決める。

$\begin{eqnarray} && (a-n)(N+m) \\ &=&aN+am-nN-nm \end{eqnarray}$

∴$b+nN=(a-n)m$
左辺は2つの非負整数の積なので、合成数が無数に作れる。