We are given the output of the following script.
```pyfrom Crypto.Util.number import bytes_to_long, isPrimefrom secret import flag, p
def encrypt(m, k, p):    return pow(m, 1 << k, p)
assert flag.startswith("TWCTF{")assert len(flag) == 42assert isPrime(p)
k = 64pt = bytes_to_long(flag.encode())ct = encrypt(pt, k, p)
with open("output.txt", "w") as f:    f.write(str(ct) + "\n")    f.write(str(p) + "\n")```
output.txt:```56022764300328750072495096443143572933197559126037376310448029893146830394734691516006436748319156766775625047434134349402808199154708521121379379634967709236749445146571233707598589136387827673809451114933178282357411603914070426899910075898048779191051239608372537055961646189065540153829233433118651021111606722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233```
We know that the flag $m$ satisfies the congruence $m^e = c \mod p$ for $e=e^{64}$.We can easily compute an $e$-th root of $c$ using sage, but it is not unique.
```pyR = GF(p)(c).nth_root(2^64)```
It holds that two $e$-th roots are equal up to a root of unity:Let $R, R'$ be two $e$-th roots of $c$ and $\alpha = R/R'$.Then $\alpha^e = R^e/{R'}^e = c/c = 1$.
This gives us an idea to solve the challenge:Iterate over all $e$-th roots of unity $\alpha$ and check if $\alpha R$ is the flag (i.e., contains `TWCTF{`).
How many roots of unity are there and how can we compute them?Let $g$ be a generator of $\mathbb Z_p^*$ ($g=3$ works).Let $\alpha = g^a$ an $e$-th root of unity.Therefore, $\alpha^e = 1$ or equivalently $ae = 0 \mod (p-1)$.Hence, $(p-1) \mid a\cdot 2^{64}$.Equivalently, $a$ must be a multiple of $(p-1)/2^{30}$, since $2^{30}$ is the largest power of $2$ that divides $p-1$.
Therefore, we can iterate all $e$-th roots of $c$ by repeatedly multiplying $R$ with $3^{(p-1)/2^{30}}$.
```pyfrom multiprocessing import Process, Queuefrom Crypto.Util.number import long_to_bytes
R = 1948865039294009691576181380771672389220382961994854292305692557649261763833149884145614983319207887860531232498119502026176334583810204964826290882842308810728384018930976243008464049012096415817825074466275128141940107121005470692979995184344972514864128534992403176506223940852066206954491827309484962494271
q = Queue()def search(start, n, notify=0x10000):    a = (p-1)//2**30    r0 = pow(3, a, p)    b = R * pow(3, a*start, p)    for i in range(n):        flag = long_to_bytes(b)        if b"TWCTF{" in flag:            print(flag)        if i % notify == 0:            q.put(notify)        b = r0 * b % p
N = 16chunk_size = 2**30//Nprocs = []for i in range(0, 2**30, chunk_size):    proc = Process(target=search, args=(i, chunk_size))     proc.start()    procs.append(proc)cnt = 0while 1:    cnt += q.get()    print(f"{cnt/2**30}")```