from secret import P, s, o, wrong, flag
from Crypto.Cipher import AES
import random, os, math

assert P * o == P.curve()(0)
assert all(math.gcd(o, w) == 1 for w in wrong + [s])
assert all(P * s != P * w for w in wrong)

key = os.urandom(32)
enc_flag = AES.new(key, AES.MODE_CTR, nonce=bytes(12)).encrypt(flag.encode())

print(f"{enc_flag.hex() = }\n{o = }")

key = int.from_bytes(key)
for i in range(32 * 8):
	P *= [random.choice(wrong), s][(key >> i) & 1]
	print(P.xy())

Ps = [eval(i) for i in open("output.txt").readlines()[2:]]

PR.<A, B> = PolynomialRing(ZZ)
polys = [P[0]^3 + A*P[0] + B - P[1]^2 for P in Ps]
B = Ideal(polys).groebner_basis()
print(B)

x = GF(p)["x"].gen()
f = x ** 3 + a2 * x ** 2 + a4 * x + a6
roots = f.roots()

# Singular point is a cusp.
if len(roots) == 1:
    alpha = roots[0][0]
    u = (Gx - alpha) / Gy
    v = (Px - alpha) / Py
    return int(v / u)

# Singular point is a node.
if len(roots) == 2:
    if roots[0][1] == 2:
        alpha = roots[0][0]
        beta = roots[1][0]
    elif roots[1][1] == 2:
        alpha = roots[1][0]
        beta = roots[0][0]
    else:
        raise ValueError("Expected root with multiplicity 2.")

        t = (alpha - beta).sqrt()
        u = (Gy + t * (Gx - alpha)) / (Gy - t * (Gx - alpha))
        v = (Py + t * (Px - alpha)) / (Py - t * (Px - alpha))
        return int(v.log(u))

E = P.curve()
q = E.base_ring().order()
n = P.order()
assert gcd(n, q) == 1, "GCD of base point order and curve base ring order should be 1."

logging.info("Calculating embedding degree...")
k = get_embedding_degree(q, n, max_k)
if k is None:
    return None

logging.info(f"Found embedding degree {k}")
Ek = E.base_extend(GF(q ** k))
Pk = Ek(P)
Rk = Ek(R)
for i in range(max_tries):
    Q_ = Ek.random_point()
    m = Q_.order()
    d = gcd(m, n)
    Q = (m // d) * Q_
    if Q.order() != n:
        continue

        if (alpha := Pk.weil_pairing(Q, n)) == 1:
            continue

            beta = Rk.weil_pairing(Q, n)
            logging.info(f"Computing {beta}.log({alpha})...")
            l = beta.log(alpha)
            return int(l)

import itertools
import sys

p = 73743043621499797449074820543863456997944695372324032511999999999999999999999

x = var("x")
Fp2 = GF(p**2, name="z2", modulus=x**2 + 1)
z2 = Fp2.gen()
Fp4 = Fp2.extension(2, name="z4")
z4 = Fp4.gen()

E0 = EllipticCurve(Fp4, [1, 0])
E0.set_order((p**2 - 1) ** 2, num_checks=0)
E0_j_invariant = E0.j_invariant()


def H(preimage):
    prev_j_invariant = E0_j_invariant
    walk = set()
    E = E0.isogeny(E0(0, 0)).codomain()

    result = 0
    # Lets surf through the graphs.
    for idx, bit in enumerate(preimage):
        sys.stdout.write(str(idx)+"->"+str(bit))
        sys.stdout.flush()

        f = E.division_polynomial(2)

        kernels = [
            cand
            for cand in sorted([E.lift_x(x) for x in f.roots(multiplicities=False)])
            if E.isogeny(cand).codomain().j_invariant() != prev_j_invariant
        ]
        assert len(kernels) == 2
        kernel = kernels[bit]

        isogeny = E.isogeny(kernel)
        domain = isogeny.domain()
        domain_j_invariant = domain.j_invariant()
        codomain = isogeny.codomain()
        codomain_j_invariant = codomain.j_invariant()
        assert domain_j_invariant != codomain_j_invariant

        prev_j_invariant = domain_j_invariant
        E = codomain

        # Please, become a trailblazer.
        assert codomain_j_invariant not in walk
        walk.add(codomain_j_invariant)

        sys.stdout.write(".")
        sys.stdout.flush()

    h = E.j_invariant()
    walk.remove(h)

    return h, walk


if __name__ == "__main__":
    msg_cnt = 3

    bit_lens = [int(sys.stdin.readline().strip()) for _ in range(msg_cnt)]
    # The preimage must be plenty long.
    assert all(bit_len >= 1024 for bit_len in bit_lens)

    preimages = [
        [
            int(c)
            for c in list(
                format(abs(int(sys.stdin.readline().strip())), f"0{bit_lens[idx]}b")
            )
        ]
        for idx in range(2)
    ]
    # Each preimage must be unique.
    assert all(a != b for a, b in itertools.combinations(preimages, r=2))

    # Takes long. Grab some coffee!
    print(preimages)
    hs, walks = zip(*map(H, preimages))
    print()
    print("hs", hs)
    print(set(hs))
    print("walks", walks)

    # I need a triple collision, which makes it triple the difficulty.
    # assert len(set(hs)) == 1
    # Can you walk?
    print([len(a & b)  for a, b in itertools.combinations(walks, r=2)])
    print([a & b  for a, b in itertools.combinations(walks, r=2)])
    assert all(len(a & b) <= msg_cnt for a, b in itertools.combinations(walks, r=2))
    assert all(len(a) >= bit_lens[idx] - msg_cnt for idx, a in enumerate(walks))

    # Here is your treat.
    sys.stdout.write(open("flag.txt").read())
    sys.stdout.flush()