平方差の形を作り出せば早く素因数分解できる？
条件：数が2つの異なる素数の積の形で表される
$ \begin{cases}a=bc\\a\in \Bbb{N}\\b,c\in\Bbb{P}\end{cases}
名前ついてた
例1.
$ 5063=83×61
$ = (72+\fbox{11})(72-\fbox{11}) = 72^2 -\fbox{11}^2
例2.
$ 1853=109×17
$ = (63+\fbox{46})(63-\fbox{46}) = 63^2 -\fbox{46}^2
四角で囲まれた数を与えられた合成数$ aから見つける方法は存在するのだろうか
$ A>a\land\exists x\in\Bbb{N};A=x^2となる$ Aを探して、$ A-xが平方数になるかどうか一つずつ試していくしか無いかな……
$ a = a \cdot 1 = \left( \frac{a+1}{2} \right)^2 - \left( \frac{a-1}{2} \right)^2で、$ aが奇数なら各項は整数
$ aが奇数なら少なくとも1通りの平方差で書ける
分数でも良ければ偶数でも書ける
Fermat’s Factorization Method ；当たりを付ける方法
合成数$ a より大きい平方数との差が平方数で表されればよい
$ 1853 < 1936=44^2
/icons/fail.icon$ 1936-1853=83
$ 1853 < 2025 =45^2
/icons/fail.icon$ 2025-1853=172
$ \vdots
$ 1853 < 3969=63^2
/icons/pass.icon$ 3969 - 1853 = 2116 = 46^2
$ \therefore 1853 = 63^2 - 46^2 = (63+46)(63-46)
任意の平方数との和を調べるのも有効
その場合、(値の大きい) 和が平方数であるか調べるのが大変
確かに
素数$ p_1, p_2 について
$ X = p_1 p_2 = \left( \frac{p_1+p_2}{2} + \frac{p_1-p_2}{2} \right) \left( \frac{p_1+p_2}{2} - \frac{p_1-p_2}{2} \right) = \left( \frac{p_1+p_2}{2} \right)^2 - \left( \frac{p_1-p_2}{2} \right)^2
$ B ≡ \left( \frac{p_1-p_2}{2} \right)^2 を$ X=p_1 p_2 から見つけるには
$ \left( \frac{p_1-p_2}{2} \right)^2 = \frac{p_1^2 +p_2^2}{4} - 2p_1p_2
$ p=2c+1 と表せることのできる自然数$ c を絞り込む
$ X =(2c_1+1)(2c_2+1) =4c_1c_2 +2(c_1+c_2) +1
$ \left( \frac{p_1-p_2}{2} \right)^2 = \frac{p_1^2 +p_2^2}{4} - 2p_1p_2
ちなみに$ p=2c+1=(c+1)^2-c^2
つまり $ \begin{cases}P_1,P_2\in\Bbb{P}\\P_1+P_2\equiv P_1-P_2\equiv 0\ (\bmod\ 2)\end{cases}が成立する$ P_1, P_2を探せばいい
これは自明だ
$ \because\forall p\in \Bbb{P};p\equiv1\ (\bmod 2)
だね。素数は奇数
ということは、以下が成立するのか
$ \forall a\in\Bbb{N}\forall p, q \in \Bbb{P}\setminus\{2\};\left\lbrack a\equiv0\ (\bmod\ pq)\implies\exist b,c\in\Bbb{N};\left\lbrack a=b^2 - c^2\right\rbrack \right\rbrack
$ \forall a\in \Bbb{N}\exists b\in\Bbb{N}\exists c\in \Bbb{N}\cup\{0\}; a=b^2 - c^2
となる
e.g.$ 15 = 5\cdot3=\left(\frac{5+3}{2}\right)^2-\left(\frac{5-3}{2}\right)^2=\left(\frac{8}{2}\right)^2-\left(\frac{2}{2}\right)^2=16-1
確かに！
$ \begin{aligned}&a = b^2 - c^2\\\iff&a+c^2=b^2\end{aligned}
https://kakeru.app/41ff5cf105892614bdcc36136c6c6e76 https://i.kakeru.app/41ff5cf105892614bdcc36136c6c6e76.svg