from itertools import count
from gmpy2 import next_prime, powmod, gcdext, gcd , isqrt
from binascii import hexlify, unhexlify
e = 2968282037100353640375137899109790499983904510372252123726372200136866453960017151334469454219618530252326391316368089337062513360207381202191915473462935477137523455963250056561696664667826520897145326882242932509636924316993816382503962649302107865422204292490659961123103322081852240437978613121365781016988448211321349469941008479597808471102164820173139919110860676464533506147455712945961147297193425603466185665772219928497258618754492859488589873906043003885893571962433509510568617898956135134801893952671289895841202079907023382879176353447845431980339763701845065932967492613174149948295178658632744337984598033199716909609691917091599333032421515584590767434316739374277008976624091929263313294017958203501962609986428734553144207841375915976037349385525685765751825435583700725710652618107250634373424713513298201017768173878869803169781015337283490319756398578109078482368725206020186761161884650413182297877151106135232838271785994275915310662858329477083914589917431343036266926436535406078268574331773960697696088892795445640924833807153106889785640164637689271399503064510417142492169690916011945805675154490404590528925067599406358567902459063109040410209462273031696409389388590120586013927889551821936657759836121166591
n = 7514486184413883943206134802309178399244378977612173666918494750761691891054947551148635071227769468578429057411933207521812645312852372491525360936618326543031520002708891330196401800722400435500157085990690437665009726219084442021182850506847121543952655588437818213790488615953323918596261471907835421407596459273791581399309405067626383928217548743866594178747621345881632069955681378662964970779524097614470204109881600043967504127490912520547758072473768719527077924134830122844355992675524808082077564650441063165395654489609498673176326527753016138066814814395200582603579511246113422000711435941608107654792503944786693356696589418688102700165482722623897706829970814110646089600275631212777003792683291735426294012686607809533096193939103941428766195023630255837719510277444701463006437791991196936648896229397094403915485049521731674097516242423233615004601202795680477677383876821794953563585797462940468885019612996080647173400509657498552114237186425176692867162493697752241051962151120715653607272964311445754089586884116532125369172407750688737448422035240971409748803419916890500367552066268915926436633178471526464741419410486387714614840372951024874043659727111073041432865136565615528171567027369016567760790667844170057
num1 = 86686136056545304660994252432156625773889066120498168631765739416745482493422987585296192063723736599263002976567595657636575621223824796036376969022114262822476015189850335269173530996691468705957636088921107674849266001665959963924041156092676589677858275687705781389349325292821902667932773664074397025014885859531985374331363919370302063677714826493469850237895535599734162522545523612723105523954370722461520363868871831877731975713014099237185479936897127467760814257390477172614268597532085496975182534809762289121382430941346377303547604540401781187289401735594268644458343791158899326073313144167027058457823531
num2 = 86686136056545304660994252432156625773889066120498168631765739416745482493422987585296192063723736599263002976567595657636575621223824796036376969022114262822476015189850335269173530996691468705957636088921107674849266001665959963924041156092676589677858275687705781389349325292821902667932773664074397025057056395971127798212868512036542986007381764450802738622888457263247853466350831762343657190118694660520926555651420001826960963517554742865635266192601411342660123373292705629287891375739175779053722758700760074451754576829084967851492233558979316397070894234154863263130900750980110998751294240297623797935181147
c = 4990981759460304744105598767593686181405870005282225829795794541021226151966053079510943795109726609634828370167775307839662644021918767556530119412853816585221569546843939870445288438295880322602517246037112564416212745954141726471664361647045729235670622890953655065235230427298013906810014221648290750692583336186843003229107021202513937560627163229698907224982160099413064560450430189221548918249561722797270239205285019947483419790983776163671611001827036804081081707549809205146146016914228431689911951835061650007130105435596899572248580145216361550470379538250892374083206633208114199207657470199269462010122511529769658733474277302308656490658251694852119519651331026206905848184310474442594518003923697214854504891077728222935182875777284193900483103844390422979429620136337089544700764854729601666550485708645758202313582038929079609869996469534041940940326632417337431671554125949585769777514656385405640728690453834779703498214246941789126527089991023766694976273980553865664242840580534044580685023115108182135139502041838131616984809782973256326815445038141870218251128685050551152554710812132312358766591390023888015234480632150114384947814031965110524912964541892010650475016456100706107619225121444952046171313017830946278
def inv_mod(a, b):
b0 = b
x0, x1 = 0, 1
if b == 1: return 1
while a > 1:
q = a / b
a, b = b, a%b
x0, x1 = x1 - q * x0, x0
if x1 < 0: x1 += b0
return x1
#p2*delta < p3
#p3*p2*delta < p3^2
#Dat p3*p2 = x
#x*delta < p3^2
# p3 > sqrt( x*delta )
# p2 = x/p3
def findP3(num):
for delta in range(5,16):
x = num*delta
x = isqrt(x)
k = 0
while ( k != 10 ):
k+= 1
x = next_prime(x)
if num % x == 0 :
print "Delta = ",delta
return x
p3 = findP3(num2)
print "P3 = ", p3
p2 = num2/p3
print "P2 = ", p2
k = p3*14
p4 = next_prime(k)
print "P4 = ", p4
p1 = num1/p4
print "p1 = ", p1
phi = 1
phi*= p1 - 1
phi*= p2 - 1
phi*= p3 - 1
phi*= p4 - 1
print "Phi = " , phi
for d_next in count(int(pow(p1 // 2, 0.5)), -1):
g, e, __ = gcdext(d_next, phi)
if (1 < e < n) and (g == 1) and (gcd(phi, e) == 1):
d = d_next
break
print "d = " , d
m = powmod(c,d,n)
print "m = " , unhexlify(format(m, "x"))