w6.py

import gmpy2
from gmpy2 import mpz

# N1 = mpz(179769313486231590772930519078902473361797697894230657273430081157732
#          6758055056206869853794492129829595855013875371640157101398586478337786
#          0692558349754108519659161512805757594075263500747593528871082364994994
#          0771895617054361149474865046711015101563940680527540071584560878577663
#          743040086340742855278549092581)
#
# N2 = mpz(64845584280807166966282426534677227872634372070697626306043907037879
#          73086180811164627140152760614175691955873218402545206554249067198924
#          28844841839353281972988531310511738648965962582821502504990264452100
#          88528167330371114229642102784028930765745864523368335707783468971583
#          8646088239640236866252211790085787877)

# N3 = mpz(720062263747350425279564435525583738338084451473999841826653057981916
#          3556901883377904234086641876639384851752649940178970835240791356868774
#          4115513201518827933181230909199624636189683657364311917409496134852463
#          9707885238799396839230364676670221627018353299443241192173812729276147
#          530748597302192751375739387929)


def one():
    A = mpz(gmpy2.isqrt(N1)) + 1
    x = gmpy2.isqrt(mpz(A**2-N1))
    # print "p:"+str(A-x)
    # print "q:"+str(A+x)
    # print "Error:"+str(A**2-x**2-N1)
    return (A-x, A+x)


def two():
    d = 1
    while d < 1048576:
        A = mpz(gmpy2.isqrt(N2)) + d
        x = gmpy2.isqrt(mpz(A**2-N2))
        if A**2 - x**2 == N2:
            print "p:"+str(A-x)
            print "d:"+str(d)
            return
        d += 1


def three():
    d = 1
    while True:
        A = mpz(gmpy2.isqrt(6*N3)) + d
        x = gmpy2.isqrt(mpz(A**2-6*N3-A))
        if A**2-A-x**2-x == 6*N3:
            p = (A-x-1)/3
            q = (A+x)/2
            print "p:"+str(p)
            print "q:"+str(q)
            print "Error:"+str(p*q-N3)
            return
        d += 1


def four():
    # cipher = mpz(2209645186741038177630656113488341801741006978789283107173183
    #              9143676135600120538004282329650473509424343946219751512256465
    #              839967942889460764542040581564748988013734864120452325229320
    #              176487916666402997509188729971690526083222067771600019329260
    #              870009579993724077458967773697817571267229951148662959627934
    #              791540)
    (p, q) = one()
    e = mpz(65537)
    phi_n = (p-1)*(q-1)
    d = gmpy2.invert(e, phi_n)
    plain = gmpy2.powmod(cipher, d, N1)
    plain = str(hex(plain))
    message = plain[plain.index('00'):].decode('hex')
    print message