from data import e, N, v, A, l, a, b, m1, m2, h
from gmpy2 import gcd
from random import randint

def factorN(n, e, d):
    """http://crypto.stackexchange.com/a/25910/17884
    
    n - modulus
    e - public exponent
    d - private exponent
    returns - (p, q) such that n = p*q
    """
    while True:
        z = randint(2, n - 2)
        k = 0
        x = e * d - 1
        
        while not x & 1:
            k += 1
            x >>= 1

        t = pow(z, x, n)
        if t == 1 or t == (n-1):
            continue

        bad_z = False
        for _ in range(k):
            u = pow(t, 2, n)

            if u == -1 % n:
                bad_z = True
                break

            if u == 1:
                p = gcd(n, t-1)
                q = gcd(n, t+1)
                assert n == p * q
                return p, q
            else:
                t = u

        if bad_z:
            continue

if __name__ == "__main__":
    R = Integers(N)
    P = PolynomialRing(R, "x")
    x = P(x)
    M = matrix(A)
    s = vector([m1^i * sum([binomial(i, j) * a^j * x^(j) * b^(i - j) for j in range(i + 1)]) for i in range(M.ncols())])
    u = M * s + a^(M.nrows()) * x^(M.nrows()) * vector(v)

    sub = [u[i].degree() for i in range(len(u))]
    d_list = [sub[l[i]] for i in range(len(l))]
    d_bin = ""

    for w in d_list:
        d_bin+= f"{w:05b}"

    d = int(d_bin,2) * h
    p, q = factorN(N, e, d)

    print(int(p).to_bytes(256))