import gmpy2

# reading ciphertext.txt as string
encoded = str(ciphertext)

# converting it into a list
enc_list = ast.literal_eval(encoded)

# decoding every item with hex, gives the result in binary
enc_list2 = [x.decode("hex") for x in enc_list]

# converting every item from binary to long format
enc_list3 = [bytes_to_long(x) for x in enc_list2]

# trial and error method yeilds two number from modulus_list have common factor other than 1
# i.e. 1st and 4th which gives us p and q. p and q are prime when checked

p = gcd(modulus_list[0], modulus_list[3])
q1 = modulus_list[0] / p
q2 = modulus_list[3] / p

# prime check
gmpy2.is_prime(p)
gmpy2.is_prime(q1)
gmpy2.is_prime(q2)

# generate r
phi1 = (p - 1) * (q1 - 1)
phi2 = (p - 1) * (q2 - 1)

# theoretically, e and phi1 should be coprime. p and q1 are prime implies they are odd which implies phi1 will be even
# e is even and hence, e and phi1 won't be coprimes. But e / 2 is odd. Below n = p * q1
# but, cipertext = (message ^ e) % n = (message^ (e1 * 2)) % n = ((message ^ 2) ^ e1) % n
# so, we can use e1 = e/2 as our exponent

e1 = e[0] / 2
e2 = e[3] / 2

# find the modulo inverse of e1 and e2
d1 = gmpy2.invert(e1, phi1)
d2 = gmpy2.invert(e2, phi2)

# here, message = (ciphertext) ^ d1) % n since, d1 is modulo inverse of e1

m1 = pow(enc_list3[0], d1, modulus_list[0])
m2 = pow(enc_list3[3], d2, modulus_list[3])

# and get square root of m1 and convert it to binary to get the flag
m1 = int(str(gmpy2.isqrt(m1)))
m2 = int(str(gmpy2.isqrt(m2)))

# both print statement gives the same answer
print(long_to_bytes(m1))
print(long_to_bytes(m2))