import gmpy2
from sympy import nextprime
from Crypto.Util.number import *
n =  131218645413263355153882609539056016131417346313857164694985244482795553321017628052409848109502464613127315618163239570703997367565089679231386965428337884937201599530967017131631155141474278378404319209291510075037073905863337674016959942427881314862079017726040171724955667479955452318495669802898606424779
cipher =  26956916426221432592724280571104585450884434311786111534684952145936843234803020133270687335772238641092604523138936635434436452351638173961249648611694741353332785924630668149684381852459140144587038595053081706954959823271114216030131967673910349569926570370812503337360887328344577462535615172014761814718
e = 65537
root = gmpy2.iroot(n,2)[0]
q = nextprime(root)
print(n % q)
p = n // q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
plaintext = pow(cipher, d, n)
print(long2str(plaintext))