# Show that if 4ab - 1 divides (4a**2 - 1)**2, then a = b.
# suppose y be a large prime and x + 1 is another large prime.

import gmpy
from Crypto.Util.number import *

# from this condition with help of previous fact we can deduce that:
# ==> we take 2a = x and b = y, so: 2xy - 1 | (x**2 - 1)**2 ==> x = 2y

# assert gmpy.is_prime(y) + gmpy.is_prime(x+1) + ((x**2 - 1)**2 % (2*x*y - 1) + 2) ** 2018 == 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146 = 1 + 1 + 2 ** 2018

# so we have x = 2y

# p = gmpy.next_prime(x**3 + y**3) # ==> p = gmpy.next_prime(8*y**3 + y**3) = gmpy.next_prime(9*y**3)
# q = gmpy.next_prime(x**2*y + y**2*x) # ==> q = gmpy.next_prime(4*y**2*y + y**2*(2y)) = gmpy.next_prime(6*y**3)
# n = p * q # ==> n = p * q ~= (9*y**3) * (6*y**3) = 54*y**6
# So we can factor n with knowing n ~= 54*y**6

n = 260272753019642842691231717156206014402348296256668058656902033827190888150939144319270903947159599144884859205368557385941127216969379550487700198771513118894125094678559478972591331182960004648132846372455712958337042783083099376871113795475285658106058675217077803768944674144803250791799957440111855021945690877200606577646234107957498370758707097662736662439460472126493593605957225541979181422479704018055731221681621886820626215670393536343427267329350730257979042198593215747542270975288047196483958369426727778580292311145109908665004662296440533724591193527886702374790526322791818523938910660223971454070731594803459613066617828657725704376475527288174777197739360634209448477565044519733575375490101670974499385760735451471034271880800081246883157088501597655371430353965493264345172541221268942926210055390568364981514774743693528424196241142665685211916330254113610598390909248626686397970038848966187547231199741
enc = 73933313646416156737449236838459526871566017180178176765840447023088664788672323530940171469589918772272559607026808711216932468486201094786991159096267208480969757088208089800600731106685561375522764783335332964711981392251568543122418192877756299395774738176188452197889668610818741062203831272066261677731889616150485770623945568369493256759711422067551058418926344060504112146971937651406886327429318390247733970549845424064244469193626197360072341969574784310397213033860597822010667926563087858301337091484951760613299203587677078666096526093414014637559237148644939541419075479462431789925219269815364529507771308181435591670281081465439913711912925412078002618729159141400730636976744132429329651487292506365655834202469178066850282850374067239317928012461993443785247524500680257923687511378073703423047348824611101206633407452837948194591695712958510124436821151767823443033286425729473563002691262316964646014201612

# now we calculate the 5th root of n//45 to find the y:

def (k, n):
   UB = 1
   while pow(UB, k) < n:
       UB *= 2
   LB = UB / 2
   while UB - LB > 1:
       M = (LB + UB) // 2
       midToK = pow(M, k)
       if midToK < n:
           LB = M
       elif n < midToK:
           UB = M
       else:
           return M
   if pow(UB, k) == n:
       return UB
   else:
       return LB

y = iroot(6, n // 54)

while True:
   if gmpy.is_prime(y):
       if gmpy.next_prime(9*y**3) * gmpy.next_prime(6*y**3) == n:
           print 'Found:', 'y =', y
           break
   else:
       y += 1

x = 2*y
p = gmpy.next_prime(x**3 + y**3)
q = gmpy.next_prime(x**2*y + y**2*x)
n = p * q
phi = (p-1)*(q-1)
d = gmpy.invert(0x10001, phi)
flag = long_to_bytes(pow(enc, d, n))
print 'flag =', flag