from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy2

key = RSA.importKey(open("publickey.pem").read())
n = key.n
e = key.e
print n
print e

for k in range(1, 1000000):
	if gmpy2.iroot(1+4*e*n*k, 2)[1] == True:
		q = (1 + int(gmpy2.iroot(1+4*e*n*k, 2)[0]))/(2*e)
		if n % q == 0:
			factor = q
			print k
			print "q: ", q
			break
ct = open("flag.encrypted").read()
ct = bytes_to_long(ct)
p = n/factor
phin = (p-1)*(q-1)
d = inverse(e, phin)
print long_to_bytes(pow(ct, d, n))
