P15. 已知 e _d n 求 p q

# 给出n,e,d, 求 q,p
<div markdown="1" style="margin-top: -30px; font-size: 0.75em; opacity: 0.7;">
:material-circle-edit-outline: 约 25 个字 :fontawesome-solid-code: 106 行代码 :material-clock-time-two-outline: 预计阅读时间 1 分钟
</div>
import random
import gmpy2


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b != 0:
        temp = a % b
        a = b
        b = temp
    return a


def getpq(n, e, d):
    p = 1
    q = 1
    while p == 1 and q == 1:
        k = d * e - 1
        g = random.randint(0, n)
        while p == 1 and q == 1 and k % 2 == 0:
            k //= 2
            y = pow(g, k, n)
            if y != 1 and gmpy2.gcd(y - 1, n) > 1:
                p = gmpy2.gcd(y - 1, n)
                q = n // p
    return p, q


def main():
    n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309
    e = 65537
    d = 9459928379973667430138068528059438139092368625339079253289560577985304435062213121398231875832264894458314629575455553485752685643743266654630829957442008775259776311585654014858165341757547284112061885158006881475740553532826576260839430343960738520822367975528644329172668877696208741007648370045520535298040161675407779239300466681615493892692265542290255408673533853011662134953869432632554008235340864803377610352438146264524770710345273439724107080190182918285547426166561803716644089414078389475072103315432638197578186106576626728869020366214077455194554930725576023274922741115941214789600089166754476449453
    p, q = getpq(n, e, d)
    print(p)
    print(q)

if __name__ == '__main__':
    main()

#coding=utf-8
from random import randint
import gmpy2
def oddR(r):
    while r%2==0:
        r=r//2
    return r

def bits(b):
    k=[]
    while b:
        if b%2!=0:
            k.append(1)
        else:
            k.append(0)
        b>>=1
    k.reverse()      
    return k

def quickmod(a,b,n):      #a^b mod n 快速幂模n运算
    f=1
    k=bits(b)
    for i in range(len(k)):
        f=(f*f)%n
        if k[i]:
            f=(f*a)%n
    return f

def gcd(m,n):
    while(n!=0):
        m,n=n,m%n
    return m

def func(e_d,N):
    k=e_d-1            
    r=oddR(k)           #求出k=2^t*r中的r

    while True:
        b=randint(2,N-1)    #获取区间(2,N-1)的一个随机数
        a=quickmod(b,r,N)   
        if a==1:            
            continue    
        y=gcd(a-1,N)
        if a>1 and y>1:    
            q=N//y
            return q
        else:
            r=r*2         

def deciphering(e_d,n):    、
    p=func(e_d,n)
    q=n//p
    phi=n-(p+q)+1
    if p*q==n:
        print p
        print q
    else:
        print"error"



n =  20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947
e_d=  100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201
deciphering(e_d,n)