素因数(5桁×5桁×6桁)までの素因数分解までは確認できた！

前回の記事の続きです。素因数分解を試すプログラムをもう少し検討した結果、大幅な軽量化と素因数分解能力の改善、強化に成功したので記録します。

前回の記事

行ったのは大幅な変更で、前回までに話した$${(ma+n)(mb+n)}$$の形を変形するとこまでは一緒ですが、そこから先は大きく変わり、コードはかなりシンプルになりました。(ただ、まだ検証がしっかりと進んでいませんが、確実に分解できるというほどではないようです。条件を取り直して何度か試せばたぶん分解できるだろうというくらいです。)

コードは以下です。

def ugojo(a,b):
    if a<0:
        a*=-1
    if b<0:
        b*=-1
    if a>b:
        a,b=b,a
    while a>0:
        a,b=b%a,a
        #print(a,b)
    return b 
def kougo2alpha(als,r1,r2,s1=1,s2=1):
    return [((r1*als[i][0]+s1)*(r2*als[i][1]+s2),[(r1*als[i][0]+s1),(r2*als[i][1]+s2)]) for i in range(len(als))]

def kougo4alpha(n,hls=[2,2],ils=[1,1]):
    ls=[[0,0],[0,1],[1,1]]
    bls=[]
    r1,r2=2,2
    #print(sls)
    i1,i2=ils[0],ils[1]
    if len(hls)>1:
        r1,r2=hls[0],hls[1]
    j=0
    print((n%(r1*r2)),r1,r2,i1,i2,'r i is?')
    while (r1*r2)**j<n:
        j+=1
    for i in range(j+3):
        #for j in range(len(ls)):
        if i>j:
            i=j
        if len(ls)>300000:
            print('memory is too big')
            return []
        ko=kougo2alpha(ls,r1,r2,i1,i2)
        print(n//(r1*r2)**(j-i))
        for k in range(len(ko)):
            #print(ko[k])
            if ugojo(abs(ko[k][1][0]),n)>1 or ugojo(abs(ko[k][1][0]),n)>1 or ugojo(abs(ko[k][0]),n)>1:
                #print('matched')
                ug=ugojo(abs(ko[k][1][0]),n)
                if ug>1 and ug!=n:
                    return [ug,n//ug]
                ug=ugojo(abs(ko[k][1][1]),n)
                if ug>1 and ug!=n:
                    return [ug,n//ug]
            q=n//(r1*r2)**(j-i)-(r1*r2)*(ko[k][1][0]//r1)*(ko[k][1][1]//r2)
            r=abs(i2*ko[k][1][0]//r1+i1*ko[k][1][1]//r2)
            s=abs(ko[k][1][0]//r1*ko[k][1][1]//r2)
            if s>0 and r>0 and (n%(s))%r!=(i1*i2)%r:
                ug=ugojo(s,r)
                #print('s',s,'ug',ug,'%s',n%(s),'%r',n%r,'r',r,n%ug)
                if ug>1 and n%ug!=1:
                    1
                    continue
            if i>5 and abs(ko[k][0])>(n*r1*r2)//(r1*r2)**(j-i) or abs(ko[k][0])<(n)//(r1*r2)**(j-i+1):
                continue
            bls+=[[ko[k][1][0],ko[k][1][1]]]   
            if q>2*r:
                if ko[k][1][1]//r2!=0:
                    #print('picked')
                    bls+=[[ko[k][1][0]//r1+(q-2*r)//(ko[k][1][1]//r2),ko[k][1][1]//r2]]                    
                if ko[k][1][0]//r1!=0:
                    #print('picked')
                    bls+=[[ko[k][1][0]//r1,ko[k][1][1]//r2+(q-2*r)//(ko[k][1][0]//r1)]]
            if q<-2*r:
                if ko[k][1][1]//r2!=0:
                    #print('picked')
                    bls+=[[ko[k][1][0]//r1+(q+2*r)//(ko[k][1][1]//r2),ko[k][1][1]//r1]]
                if ko[k][1][0]//r1!=0:
                    #print('picked')
                    bls+=[[ko[k][1][0]//r1,ko[k][1][1]//r2+(q+2*r)//(ko[k][1][0]//r1)]]

        ls=bls
    return [] 
def controller(n,r):
    ni,j=2**r,n%2**r
    
    for i in range(1,ni**2):
        if i%ni==0:
            continue
        pr=kougo4alpha(n,[ni,ni],[2*i+1,ni-j+i*4])
        if len(pr)>1:
            return pr
    return []

p=780733*906751981

print(controller(p,4))

$${s=(pa+1)(qb+1)}$$について$${a→pa+1、b→qb+1)}$$と順々にaとbの大きさを変えて持ち上げて、その間にa、bと元の数nとの差分から、もし仮にsが元の数の倍数であった時に満たす条件を満たせるように、値を細かくずらしていくのが大まかな流れです。pとqはそんなに条件に制約がなさそうなので、数字が小さいとメモリに溜め込む数が増えてメモリ落ちするので、メモリ落ちしない程度の2から19くらいまでの小さな素数や、その累乗を使うといいかもしれません。pとqが別の値を取る時の動き方をしっかりと検証した訳ではないですが、pとqはおそらく同じ値の方が、正しい挙動に近くなる点があるだろうとは思います。一応、後で修正します。

今少しだけ挙動を確認しましたが、5桁×5桁×6桁くらいの数は一応時間をかけた上で分解することができたようです。

分解を確認した数: 65719*487387*50387(p、qが11、11で分解を確認)
65719*3293724794959(p、qが31、17で分解を確認)
328901*41434319

メモリをうまく使えば、もう少し行くんでないだろうか？→上手くいきました。ほんとに唖然とするくらいに…目標であった10進で積の形の16桁まであっという間に制覇しました。RSA暗号破れる可能性があるかもしれない…ガチで、、

考え方

もし、nが２つ以上の素数の積であったとすれば、$${n=(pa+1)(qb+1)}$$の形で表すことができるpとqとaとbの組み合わせが必ず１つ以上見つかるはずです。もしこれを満たすpとqの組み合わせであれば、変形して、$${n=(pa+1)(qb+1)=pqab+pa+qb+1}$$となり、pqでnを割った余りは$${pa+qb+1}$$に必ずなるはずです。これは、出てきた余りをさらにpとqで割ってみることで、検証することができます。そこで、pとqを固定したまま、aとbを動かして、aとbの積を少しずつ大きくしていくとどうなるのかを確認してみるのが今回のプログラムとなります。pとqが目的となる因数をそれぞれで割ると1余る数であれば条件は良さそうですが、そうでない場合には複数回pとqを変更して求め直さないといけないかもしれません。

この記事のコードは以下で更新中です。