We are given the output of the following script.

```py
from Crypto.Util.number import bytes_to_long, isPrime
from secret import flag, p

def encrypt(m, k, p):
return pow(m, 1 << k, p)

assert flag.startswith("TWCTF{")
assert len(flag) == 42
assert isPrime(p)

k = 64
pt = 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:
```
5602276430032875007249509644314357293319755912603737631044802989314683039473469151600643674831915676677562504743413434940280819915470852112137937963496770923674944514657123370759858913638782767380945111493317828235741160391407042689991007589804877919105123960837253705596164618906554015382923343311865102111160
6722156186149423473586056936189163112345526308304739592548269432948561498704906497631759731744824085311511299618196491816929603296108414569727189748975204102209646335725406551943711581704258725226874414399572244863268492324353927787818836752142254189928999592648333789131233670456465647924867060170327150559233
```

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.

```py
R = 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}}$.

```py
from multiprocessing import Process, Queue
from 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 = 16
chunk_size = 2**30//N
procs = []
for i in range(0, 2**30, chunk_size):
proc = Process(target=search, args=(i, chunk_size))
proc.start()
procs.append(proc)
cnt = 0
while 1:
cnt += q.get()
print(f"{cnt/2**30}")
```