巨大な自然数の素因数分解を、多項式の解計算のプログラムを使って実現してみる。
前回の記事はこちらです。
前回の記事に書いた、xの多項式の解を計算するプログラムを使って、自然数の素因数分解を実現することができましたので、紹介します。
以下がプログラムです。前回のプログラムを書き込んだpythonファイルの下に、追記して使います。
使い方
①hantei変数に求めたい数字を書き込む(この変数に入った数字を素因数分解します。
②tei変数に3以上のなるべく小さい数を初期値に入力します。この変数の数値を元に、求めたい数値を余りのある割り算で組み立て除法して、因数の候補を計算していきます。整数である必要はありません。
③kumiawasemax変数に、因数の候補がたくさん発生した場合の計算量を、どこまで中断させずに続けるかの計算回数の上限を入力します。あまりにも大きすぎる場合は計算が終わらなくなるため、強制終了させる必要が生じます。恐らく100で十分でしょう。
④実行します。teiの数値を、決められた法則に合わせて少しずつ増加させながら、整数でない数を含む因数分解の計算を40回ほど進めて、これを50×5セット反復します。因数分解した中に、一つでも整数が見つかれば、停止します。因数が見つかっていなくても、求めたい数を割り切れる数が一つでも見つかった場合は、同じように停止します。
因数分解を実際に実行しているスクショになります。
hantei=143279365439677548941
n=hantei
tei=5
kumiawasemax=300
minlist=[0.1]*41
kailist0=[0]*41
teilist=[0]*41
teilist2=[0]*50
sabuntei=[0]*50
tmptei=tei
trued=False
count=0
tr2=0
while tr2<50:
tr2+=1
tei-=1#*(tmptei-tei)
for tr in range(41):
tei+=0.05#*abs(tmptei-tei)
n=hantei
jigen=math.floor(math.log(n,tei))-1
#print(math.log(n,tei),'jigen')
bitlist=[]
while n>0:
shou=n//tei
amari=n-shou*tei
n=shou
#n,amari=divmod(n,tei)
bitlist.append(amari)
bitlist.reverse()
jigen=len(bitlist)-1
if tr==11:
print(bitlist)
kailist=kyuukai(bitlist)
start=time.time()
#print(jigen,'jigen')
#print(kailist,'kailist')
minsa =0.1
num=0
maxkumi=2**jigen-1
if maxkumi>kumiawasemax:
maxkumi=kumiawasemax
for i in range(1,maxkumi):
kumi=i
kumilist=[0]*jigen
for k in range(jigen):
kumi,amari=divmod(kumi,2)
kumilist[k]=amari
tamesi=1
for j in range(len(kailist)):
if kumilist[j]==1:
tamesi*=tei-kailist[j]
sa=abs(tamesi-round(abs(tamesi)))
#print(sa<minsa)
if sa<=minsa and abs(tamesi)<(hantei**0.5):
minsa=sa
num=tamesi
if (hantei/int(round(abs(tamesi)))).is_integer() :
print(tamesi,int(round(abs(tamesi))),hantei/int(round(abs(tamesi))),'ok',kumilist,abs(tamesi-round(abs(tamesi))),tamesi.real-round(tamesi.real))
trued=True
#print (sa,minsa,tamesi)
minlist[tr]=minsa
kailist0[tr]=num
teilist[tr]=tei
if trued:
break
#print(teilist2)
#print(kailist,'kotae')
min2=0.1
for i in range(21):
if minlist[i]<min2:
tei=tei+(kailist0[i].real-tei)/2+minlist[i]
min2=minlist[i]
#print(minlist)
#print(kailist0)
#print(teilist)
sabuntei[tr2]=tei-tmptei
print(tei)
tmptei=tei
teilist2[tr2]=tei
if tr2==48 and count<5:
tr2-=48
count+=1
if trued:
break
print(teilist2)
#print(lists)
print(minlist)
print(kailist0,kailist)
print(teilist)
print('time is ',time.time()-start)
print(sabuntei)
print(hantei,trued)メカニズム
ある数Dをn個の数に因数分解することを考えるとする。ある数x<<Dを考えて、Dをxの多項式で表す。
$${D=a_0 x^n+a_1 x^{n-1}+…+a_{n-1} x+a_n}$$
このxの多項式を、xが未知数でDが0とした場合の解xを求めるものと仮に考えて、xの方程式を解く。今回は、xの多項式を因数分解するためのプログラムを使い、一意に分解できる。$${x=λ_1,λ_2…}$$この解を使って元の式を変形する。
$${D=a_0 (x-λ_1)(x-λ_2)…(x-λ_n)}$$
$${a_0}$$の係数を残したままxの全ての解を見せる形式に変形すると、Dの数値をそのままに、Dがn個の数$${(x-λ_k)}$$で掛け算した数であることを示すことができます。そこで、$${(x-λ_k)}$$のうちいくつか適当なものを選び、それぞれの積を取った時、その積が自然数となるのであれば、それはDの素因数の積のうちの一つであることがわかります。
値の更新のしかた
Dを自然数とした時に、Dをxで割った余りをDが0より小さくなるまで繰り返して、出てきた余りの数の組み合わせをxの係数として表すことができます。また、xの係数は全て自然数であるため、これを因数分解して出てきた項は、もし実数であれば、基本的にxよりも大きな数になりやすいです。そのため、因数分解して出てきた項のうち、より整数に近い項を選んで次のxに選べば、常に加算することになりやすいです。
そうして選んだxとその方程式の解から算出した数値x-λについて、xとx-λの数値の差がほとんどないかつ整数であるxを停止条件として設定すれば、収束は遅いながらも、整数の因数を検出できるプログラムにすることができます。