"""ecrsa (BlackAlps) -- KMOV on y^2 = x^3 + b mod n.

Flaw: the flag is short, so encode() left-pads it into the second half and
m1 = 0.  M = (0, m2) is an inflection point of y^2 = x^3 + b: 2M = -M, so M
has order 3 and C = e*M = (e mod 3)*M = 2*M = -M.  Hence M = -C = (0, n - cy),
no key needed.  (The intended route, matching the flag text: for p = 2 mod 3
every curve y^2 = x^3 + b mod p is supersingular with order p+1, and p+1 is
smooth, so a random point times a smooth bound leaks p -- see factor().)

Usage: python3 -I solve.py files/output.txt
"""
import re
import sys
from math import gcd
import random


def inv(a, n):
    g = gcd(a % n, n)
    if g != 1:
        raise ZeroDivisionError(g)
    return pow(a, -1, n)


def add(P, Q, n):
    if P is None:
        return Q
    if Q is None:
        return P
    (x1, y1), (x2, y2) = P, Q
    if x1 == x2 and (y1 + y2) % n == 0:
        return None
    if P == Q:
        lam = 3 * x1 * x1 * inv(2 * y1, n) % n
    else:
        lam = (y2 - y1) * inv(x2 - x1, n) % n
    x3 = (lam * lam - x1 - x2) % n
    return x3, (lam * (x1 - x3) - y1) % n


def mul(k, P, n):
    R = None
    while k:
        if k & 1:
            R = add(R, P, n)
        P, k = add(P, P, n), k >> 1
    return R


def primes(B):
    s = bytearray([1]) * (B + 1)
    s[0] = s[1] = 0
    for i in range(2, int(B ** 0.5) + 1):
        if s[i]:
            s[i * i::i] = bytearray(len(s[i * i::i]))
    return [i for i in range(B + 1) if s[i]]


def factor(n, B=200000):
    """p+1 attack via supersingular y^2 = x^3 + b (random point, random b)."""
    P = (random.randrange(n), random.randrange(n))
    try:
        for q in primes(B):
            qk = q
            while qk * q <= B:
                qk *= q
            P = mul(qk, P, n)
            if P is None:
                return None
    except ZeroDivisionError as z:
        g = z.args[0]
        return g if 1 < g < n else None
    return None


def main(path):
    v = dict(re.findall(r"(\w+)\s*=\s*(\d+)", open(path).read()))
    n, e, cx, cy = (int(v[k]) for k in ("n", "e", "cx", "cy"))
    C = (cx, cy)
    assert cx == 0, "shortcut needs m1 = 0"
    M = (0, (-cy) % n)
    assert mul(e, M, n) == C
    k = (n.bit_length() - 1) // 8
    flag = (M[0].to_bytes(k) + M[1].to_bytes(k)).lstrip(b"\0")
    print(flag.decode())
    if "--factor" in sys.argv:
        p = factor(n)
        print("p =", p, "q =", n // p if p else None)


if __name__ == "__main__":
    main(sys.argv[1])