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))