素因数分解

A入力数値を素因数分解し結果をカンマ区切りでCへ出力します
ホームへ

内部処理:

内部では
1:試し割で素数30029までの素数を取り出し、その後以下の順で素因数分解を試みます
2:フェルマーのアルゴリズム(ループ最大は1000000回から10000回に変更)
3:ポラードのp-1法(ループ最大は10000回)
4:ウィリアムズのp+1法(ループ最大は10000回)
5:ポラードの ρ 法(ループ最大は5000000回)14桁の素数までは対応できそうです
の順で行われます最後まで成功しなかった場合1分以上待たされる事もあります
答えが出なかった場合も取り出した素数と残った合成数をカンマ区切りでCへ出力します
※二次ふるい法はメモリを使わずに高速化ができそうにないので諦めました

大整数電卓ツール使ってみてください

高速化:

フェルマーのアルゴリズムの高速化で 参考サイトでは二乗計算を足し算に置き換えて 高速化をしていますが、ここではY 側の処理に注目し高速化を試みました Y 側の終了は元の合成数より小さくなるか等しくなるまでループします、このループ回数は
m:X側からの数値でこれのみが変数 n:元の合成数とすると
Y 側ループ回数を求める式は:r(1+m-n)-1 になり
 1+m-n=N×N となる時が答えなのです
ここまででサイトにアップしていましたが今回更に高速化ということで
 1+m-n=N×N に注目し、平方根が余りのない整数の時が答えになるので平方根を計算する前に値が整数の二乗かを試し、 そうでなければ何も計算せずX 側のループへ戻します、具体的には整数の二乗の平方剰余がとる値は決まっているので、 それを使って判断しています但し剰余を試す数値は複数
(256,97,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67) を試し結果として10万分の一以下まで無駄なルート計算を抑えることができました
実験では40万回ループするデータで最後まで残ったのは2個でそのうち一個は正解なので 無駄なルート計算をしたのは一回のみでした。
今回更に見直して素数同士の差に注目し合成数をN 差をK 和をH とすると √(H×H-4N)でKが求まるので√が整数になるHを探し答えKが求まると (H+K)÷2と(H-K)÷2が素数の答えになります。これによりほんの数パーセントですが高速化できました。
更に見直して最初からHとKは2の倍数なので先に2で割り√(H×H-A)でKを求めます。
ここで素数をそれぞれ(2*n+1)と(2*m+1)と置くと
(2*n+1)*(2*m+1)=4nm+2*n+2*m+1=a なので (a-1)%4=0 なら(2*n+2*m)も4で割り切れ故に((2*n+1)+(2*m+1))/2=H
((2*n+1)-(2*m+1))/2=Kなので H%2=1 K%2=0 となる
(a-1)%4=2 なら H%2=0 K%2=1 となるのでHの初期値を(A-1)%4により、それぞれ偶数または奇数に固定して2個飛ばしでループさせれば
ループ回数は二分の一となります。結果(H+K)と(H-K)が素数の答えになります
これでも8桁×8桁の素数で3秒弱かかります、まだまだですね。

私見:

個人的に好きなのはフェルマーのアルゴリズムで他でも10桁の素数が答えとして表示されるのは「すごいな」とは思いますが2000桁の合成数から1000桁の 素数が0.079秒で出力された時は「おおぉぉ!」と声が出てしまいます、頭では直ぐに答えが出ると分かっていても、やっぱり感動してしまいます。 「大整数電卓」には「C数式計算」の例として「フェルマ素因数分解実験用合成数作成」がありますが 100桁の素数なら素数を作るのも一瞬ですが1000桁だと 素数を見つけるだけでも大変です次の素数まで1万以上離れてることがあるので運が悪ければ一つの素数を得るのに3分以上かかる事もあります、そうやって時間をかけて 作った合成数が一瞬で素因数分解できるのは感動です(勿論前提として上位500桁が同じで下位500桁のみが違う素数同士を掛け合わせた合成数である事)
ただ悲しいのは、これが役立つ場面を思いつかないということです

注1:
素数関連の大部分をこのサイトを参考に作成しました

参考実験:フェルマーのアルゴリズム

2022年9月10日追記:多少アルゴリズムに手を加えて高速化をしてみました。なのでループ最大を1000回から10000回に変更しました
※30029までの素数試し割の時間も含んだ時間です

100桁の素数2個

で合成数を作り(上位指定桁は同じ数字)素因数分解を実行し掛かる時間を測定
実験:
上位50桁下位50桁で作成 
ループ回数 1  時間:0.002秒
合成数:52858573889305743368658801063041665538718710338038853961324172302766003175664506178472769865011015541977383988386619930788475147151430487787352101919076418548905001687630451627636550434944086829403743
素数1:7270390215752229028954049927225296301029984559592760155262844718140352046233180312909284722021061017
素数2:7270390215752229028954049927225296301029984559592777181805164002077510013670899123190287390083140279
実験:
上位49桁下位51桁で作成 
ループ回数 3  時間:0.002秒
合成数:72832157829248889731356108622846985599381920392691908622628397724361218318867137880127433525501869724997613003147033165943836923219760802646755876706310814947760304639628990816636082052143567580019899
素数1:8534175872880104275555614251992984532274548096045090862962962798491207089453308687259968275080787221
素数2:8534175872880104275555614251992984532274548096045520695538628190226546298414171566902547726239448719
実験:
上位48桁下位52桁で作成 
ループ回数203 時間:0.024秒(高速化で0.002秒)
合成数:82357115638223436220151206427545901491774666127458816854641975199618335823958431965195090693490876974828212163655663910630553917152066492408207554437566472405994717839523700408514727323013969250060877
素数1:9075082128456107598762172452148705589894531871820970404759524024151044563722727343056662057892088049
素数2:9075082128456107598762172452148705589894531871824800591582544332596504513680002949878798823799551773
実験:
上位47桁下位53桁で作成 
ループ回数19175 時間:ループ回数:1.782秒(高速化で0.014秒)
合成数:42921444914596261758088196610731424550473736982628240796451549688266970428034284693073033661905352838442717888885427557015880559390817049676688167524272347718174081925415724656422849975091418840546379
素数1:6551446017071060454948960241312316634969077078751047396068281086181522771123058901689200690737926697
素数2:6551446017071060454948960241312316634969077078719346180193868480170072197497360433499581680483463507
実験:
上位46桁下位54桁で作成 
ループ回数2335981 時間:解答なし (高速化で1.238秒 ※実験のためループ最大を更に上げてます本来は解答なしです)
合成数:39213050304637444684036553893543655495609342688871264495680980780311335917803385323701179053280481670953924866015868928357336836947650062515939026249962399260563894015735497075880912433492669209115639
素数1:6262032441998160447093109335698069371780834996497565828100454428349887209533407287853294122489757957
素数2:6262032441998160447093109335698069371780834996155478274562613856218040715589956147240580750909524427

10桁の素数2個

で合成数を作り(上位は同じ数字)素因数分解を実行し掛かる時間を測定
実験:
上位5桁下位5桁で作成 
ループ回数 1  時間:0.000秒
合成数:1154438269757072357
素数1:1074421109
素数2:1074474673
実験:
上位4桁下位6桁で作成 
ループ回数 9  時間:0.001秒
合成数:12022413297471709849
素数1:3467573971
素数2:3467096419
実験:
上位3桁下位7桁で作成 
ループ回数 572 時間:0.004秒(高速化で0.001秒)ループ回数を計算しないでオリジナルのままループを回すと58.508秒でした
合成数:33702924732749238353
素数1:5807998327
素数2:5802846839
実験:
上位2桁下位8桁で作成 
ループ回数 9726 時間:0.067秒です(高速化で0.005秒)
合成数:27164434013085267377
素数1:5201892133
素数2:5222029469
実験:
上位1桁下位9桁で作成 
ループ回数 4543358 時間:解答なし(高速化で1.457秒 ※実験のためループ最大を更に上げてます本来は解答なしです)
合成数:19345006149443720197
素数1:4602805939
素数2:4202872423

因みに普通の素因数分解

も7桁×7桁までならできます
実験:
7桁×7桁で作成 
ループ回数 391854 時間:解答なし(高速化で0.141秒)
合成数:44644177321333
素数1:4751849
素数2:9395117
実験:
7桁×7桁で作成 
ループ回数 915229 時間:解答なし(高速化で0.28秒)
合成数:10997982970057
素数1:1603237
素数2:6859861