素因数分解、目下更新中のコード置き場

アールル 
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],[1,0]]
    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
    if j<5:
        j=5
    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,t=20):
    ni,j=2**r,n%4**r
    q=1
    for i in range(ni):
        l=1
        m=1
        qls=[]
        while len(qls)==0 and l<t:
            #print(q)
            q+=2**l
            for s in range(q):
                if (n%2**t+4**l*s)%q==0:
                    while (n%2**t+4**l*s)%q==0 and (j+4**l*s)>0 and l<t:
                        qls+=[(n%2**t+4**l*s)//q]
                        l+=1
                    else:
                        m=s
                        continue
                    l+=1
                    m=s 
        qls=list(set(qls))
        for jj in range(len(qls)):
            #print(q,m,qls[jj])
            x,y=j-q+1,j-qls[jj]+1
            pr=kougo4alpha(n,[ni,ni],[x,y])
            if len(pr)>1:
                return pr
    return [] 
p=2000497*2002579 
print(controller(p,6,10))

2000497*2002579にて素因数分解を確認
p=2139107*2103011*2138387にてcontroller(p,7,12)条件で2139107, 4497051383257への分解を確認(2024/1/24)

この記事で更新しているプログラムの説明が書かれている記事

⭐︎参考情報

ヘンゼルの持ち上げ補題

この記事が気に入ったらサポートをしてみませんか？