from Crypto.Util.number import long_to_bytes, inverse

p = 9109516638675942224743777995148545134530013554275734886455448931671863095997507569243594319863772181509837924098591463427796446396931029539716403962408943
q = 10740686879425642178311117871838817113230054398803925695044823186721569157087087148128828336409020272313601366223259400603169731251187486908754100440733959
c = 140655211554927678503347324092478047438045251131293471286425677406100240063574753515992620829045521915462201396598103882338968738138846160402436956319724406025
n = p * q

1. 计算 m_p 和 m_q

mp = pow(c, (p + 1) // 4, p)
mq = pow(c, (q + 1) // 4, q)

2. 使用扩展欧几里得算法辅助 CRT

yp * p + yq * q = 1

根据 CRT 公式：x = (mqypp + mpyqq) % n

yp = inverse(p, q)
yq = inverse(q, p)

3. 组合出 4 个解

res1 = (mq * yp * p + mp * yq * q) % n
res2 = (mq * yp * p - mp * yq * q) % n
res3 = (-mq * yp * p + mp * yq * q) % n
res4 = (-mq * yp * p - mp * yq * q) % n

for m in [res1, res2, res3, res4]:
flag = long_to_bytes(m)
if b'flag' in flag:
print(f"[+] Found Flag: {flag.decode()}")