非整数論的因数分解

非整数論的因数分解

　祖父が、妙なコラムをkakuyomuに投稿していたのを見つけた。　祖父は、ラノベを投稿した後で、アポ電強盗に襲われて死亡したらしい。私が生まれる前の話だ。

　祖父のメモによれば、N=p*q　として　R=q/p　とした場合、Rが整数または簡単な有理数になっている場合は、Nを素因数分解できるらしいが、Rを推定するのが難しく、せいぜい3桁くらいの精度しか計算できなかったらしい。

　大きな2つの素数p,qの積をNとする。

　一般に、Nを素因数分解するのは難しいといわれている。

　数体篩を用いて分解するのが常識となっている。

　量子コンピュータのおかげで、かなりの桁数の合成数が素因数分解できるようになったので、いまさら普通のコンピュータで素因数分解の方法を検討するのはあまり意味がないが、　祖父の意思を継いで、素人として、非常にばかばかしい方法を思いついたので試してみた。Nの上位桁からp,qの上位桁を逐次推定していく方法である。

　Nの最上位の2桁N2とほぼ等しくなるような、整数の積u*vを考える。

　ここで、ruv=v/u とする。　u ≦ v　とする。

　評価関数としてdn=N2-u*v と　f=（(N2/ruv）^1/2）-u を用いる。

　無駄な計算を省くために、dnやfは適当な制限を加えておくと良い。

　桁数に応じてdnは大きく、fは小さくする。

　uとvを1から10まで変えながら

　ruv、dn、fを計算する。

　この中で、dnとfが同時に小さくなるu,vの組を候補にする。

　次に、Nの最上位4桁をN4として上記と同様の計算を10*uと10*vの近傍で行う

　u vs f またはv vs fをグラフにすると、下に凸の二次曲線のような形になる。

　グラフは「点」でプロットする。腺でつなぐと非常に見難い。

　注意事項として,p、qの桁数は不明なので、ここで得られたruv=v/uは、その値が10倍や100倍になる可能性がある。

　Nの桁数の上位1/4桁程度まで推定できたら、次にそのときのruvとNから

　pの推定値　(N2/ruv）^1/2

　qの推定値　ruv*(N2/ruv）^1/2

　を計算する。

　Nと10*ruv、Nと100*ruv、Nと1000*ruvで同様の推定値を計算する。

　推定したruvが非常に整数に近い場合、Nを因数分解できる。

　逆にNの下位からp,qを推定しようとすると、最初の2桁程度で挫折することになる。

　Nの素因数分解を困難にしている原因は、加法には一意性がない点である。

　例えば9という数は0+9から1+8、2+7・・・・・・・7+2、8+1、0+9まで可能性がある。

　これが原因で、簡単に計算量が爆発的に増加する。

　数値例を示しておこう。

　p=2122150059876543181

　q=63664501796296295467

　N=135105626299020474328081251400160060527

　R=30.0000000000000000174351478246323862174...............

　Nは39桁なので，10^37で割って四捨五入すると14になる．N2=14

　vを2から10，　uを2から10まで変えながら

　nuv=u*vとruv=v/uとdn=N2-nuvと(N2/ruv)^(1/2)-uを計算する．

　これより，　u=3，v=6　nuv=18　ruv=　2.000000　dn=2　f=0.3542487が候補となる．

　次にNを10^35で割って四捨五入すると 1351

　uとvを10倍し　その上下10程度の範囲で同様の計算を行う。

　ここでは，最低点の候補がわからないので，次に進む

　Nを10^33で割って四捨五入すると 135106

　u, vを10倍して計算してみると，グラフ上に放物線のような軌跡が現れる

　uが212付近，vが637付近

　Nを10^31で割って四捨五入すると 1351056263

　同様の計算をすると，下に凸のグラフが明瞭に現れる。

　ここまでくれば，vは63660と63669　uは21219と21224の間にあることがわかる．

　さらに絞り込むためにNを10^29で割って四捨五入して135105626299

　同様に2桁ずつ精度を上げていくとp,qの上位9桁まで推定でき、　Rの推定値は3.00000000000....となる。

　ここでNとRの推定値からp,qを推定すると

　Rが3の場合

　pの推定値=6710827725872581049

　qの推定値=20132483177617743173

　R30の場合

　pの推定値=2122150059876543181

　qの推定値=63664501796296295467

　Rが300の場合

　qの推定値=671082772587258121

　qの推定値=201324831776177432143

　正しいp，qは

　p=2122150059876543181

　q=63664501796296295467

　　R=30の場合が正しい結果を与える。

　Rの推定値の誤差が小さい場合は，p，qの推定値の誤差もそれほど大きくないので，力任せに計算してもそれほど計算量は増えない。　祖父が見つけた方法で、グラフから求めることもできる。

　この方法は、任意のN=pqで素因数分解に使えるわけではないようだ。

　手作業や、グラフの目視による確認作業が必要なため、作業は煩雑だが、指数関数的な計算量の爆発は起こらない。

　運が悪いと、グラフから最適な候補を決められない場合がある。