PA6.py

import gmpy2
import binascii
gmpy2.set_context(gmpy2.get_context())
gmpy2.get_context().precision=1050
def question1():
    N=gmpy2.mpfr("179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581",1050)
#print("N",N)
    A=gmpy2.ceil((gmpy2.sqrt(N)))
    #print("A:",A)
    k=gmpy2.square(A)-N
    #print("K:",k)
    x=gmpy2.ceil( gmpy2.sqrt(k))

    print("x:",x)
    p=A+x
    q=A-x
    if(N==gmpy2.mul(p,q)):
        if(p>q):
            p,q=q,p
        print("found pq:",p,q)
def question2():
    #25464796146996183438008816563973942229341454268524157846328581927885777969985222835143851073249573454107384461557193173304497244814071505790566593206419759

    N=gmpy2.mpfr("648455842808071669662824265346772278726343720706976263060439070378797308618081116462714015276061417569195587321840254520655424906719892428844841839353281972988531310511738648965962582821502504990264452100885281673303711142296421027840289307657458645233683357077834689715838646088239640236866252211790085787877",1050)
    A=gmpy2.ceil((gmpy2.sqrt(N)))
    #print("A:",A)
    i=1
    while i<2**20:
    #print("K:",k)
        x=gmpy2.ceil(gmpy2.sqrt(gmpy2.square(A)-N))

        #print("x:",x)
        p=A+x
        q=A-x
        if(N==gmpy2.mul(p,q)):
            if(p>q):
                p,q=q,p
            print("found pq:",p,q)
            break
        A+=1
        i+=1
def question3():
    N=gmpy2.mul(gmpy2.mpz("720062263747350425279564435525583738338084451473999841826653057981916355690188337790423408664187663938485175264994017897083524079135686877441155132015188279331812309091996246361896836573643119174094961348524639707885238799396839230364676670221627018353299443241192173812729276147530748597302192751375739387929"),6)
                        
    A=gmpy2.ceil(gmpy2.sqrt(N))#A-N^(1/6)<neg
    k=gmpy2.sub(gmpy2.square(A),N)
    print(k)
    x=gmpy2.ceil(gmpy2.sqrt(k))#same trick to calculate the other half to recover p,q (3p-2q)/2
    print("x:",x)
    p=(A-x)/2
    q=(A+x)/3
    print("p:",p,"q:",q)
question3()
def question4():
    N=gmpy2.mpz("179769313486231590772930519078902473361797697894230657273430081157732675805505620686985379449212982959585501387537164015710139858647833778606925583497541085196591615128057575940752635007475935288710823649949940771895617054361149474865046711015101563940680527540071584560878577663743040086340742855278549092581")

    ct=gmpy2.mpz('22096451867410381776306561134883418017410069787892831071731839143676135600120538004282329650473509424343946219751512256465839967942889460764542040581564748988013734864120452325229320176487916666402997509188729971690526083222067771600019329260870009579993724077458967773697817571267229951148662959627934791540')
    e=gmpy2.mpz(65537)
    p=gmpy2.mpz("13407807929942597099574024998205846127479365820592393377723561443721764030073662768891111614362326998675040546094339320838419523375986027530441562135724301")
    q=gmpy2.mpz("13407807929942597099574024998205846127479365820592393377723561443721764030073778560980348930557750569660049234002192590823085163940025485114449475265364281")
    phi=gmpy2.mul(p-1,q-1)
    d=gmpy2.invert(e,phi)
    pt=gmpy2.powmod(ct,d,N)
    print(binascii.unhexlify(hex(pt)[hex(pt).find("00")+2:]))
    #print(binascii.unhexlify())
question4()