BVA1

from copy import deepcopy
from numpy import floor, ceil
from random import randint, shuffle
from math import gcd


def find_full_index(mu, s, k):
    for i in range(0, len(mu)):
        if mu[i][0][0] == s and mu[i][0][1] == k:
            return i


def calc_r(mu_znach):
    if mu_znach > 0:
        r = floor(1 / 2 + mu_znach)
    else:
        r = -floor(1 / 2 - mu_znach)
    return int(r)


def print_matrix(M):
    for i in M:
        print(i)


def gram_schmidt(a):
    k = len(a[0])
    N = len(a)
    b = [[0] * k for i in range(N)]
    b[0] = a[0]
    mu = list()
    B = list()
    b_znam = 0
    for n in range(k):
        b_znam += b[0][n] * b[0][n]
    B.append(b_znam)
    for i in range(1, N):
        sum = a[i]
        for j in range(0, i):
            scolar_ab = 0
            scolar_bb = 0
            proj = [0 for i in range(k)]
            for n in range(k):
                scolar_ab += b[j][n] * a[i][n]
                scolar_bb += b[j][n] * b[j][n]
            indexes = tuple([i + 1, j + 1])
            m = list([indexes, scolar_ab / scolar_bb])
            mu.append(m)
            for n in range(k):
                proj[n] = (scolar_ab / scolar_bb) * b[j][n]
            for n in range(k):
                sum[n] -= proj[n]
        b[i] = sum
        b_znam = 0
        for n in range(k):
            b_znam += b[i][n] * b[i][n]
        B.append(b_znam)
    return b, mu, B


def LLL_algh(ai_basis):
    bi_basis = deepcopy(ai_basis)  # Вместо ссылки создаем новую переменную, чтобы не затереть ai
    orth_basis, mu, B = gram_schmidt(bi_basis)
    n = len(orth_basis)
    k = 2  # Положить k = 2
    while 1:
        number = find_full_index(mu, k, k - 1)
        mu_num = mu[number][1]
        if abs(mu_num) > 1 / 2:
            r = calc_r(mu_num)
            for i in range(0, len(ai_basis[k - 1])):
                ai_basis[k - 1][i] -= r * ai_basis[k - 2][i]
            for j in range(1, k - 1):
                id_k = find_full_index(mu, k, j)
                id_k_1 = find_full_index(mu, k - 1, j)
                mu[id_k][1] -= r * mu[id_k_1][1]
            mu[number][1] -= r
            mu_num = mu[number][1]
        if B[k - 1] < (3 / 4 - mu_num ** 2) * B[k - 2]:
            B_t = B[k - 1] + mu_num ** 2 * B[k - 2]
            mu[number][1] = mu_num * B[k - 2] / B_t
            B[k - 1] *= B[k - 2] / B_t
            B[k - 2] = B_t
            ai_basis[k - 1], ai_basis[k - 2] = ai_basis[k - 2], ai_basis[k - 1]
            if k > 2:
                for j in range(1, k - 1):
                    id_k = find_full_index(mu, k, j)
                    id_k_1 = find_full_index(mu, k - 1, j)
                    mu[id_k][1], mu[id_k_1][1] = mu[id_k_1][1], mu[id_k][1]
            for s in range(k + 1, n + 1):
                id_s = find_full_index(mu, s, k)
                t = mu[id_s][1]
                id_s_k_1 = find_full_index(mu, s, k - 1)
                mu[id_s][1] = mu[id_s_k_1][1] - mu_num * t
                mu[id_s_k_1][1] = t + mu[number][1] * mu[id_s][1]
            k = max(2, k - 1)
        else:
            for l in range(1, k - 1)[::-1]:
                ind = find_full_index(mu, k, l)
                mu_zn = mu[ind][1]
                if abs(mu_zn) > 1 / 2:
                    r = calc_r(mu_zn)
                    for i in range(0, len(ai_basis[k - 1])):
                        ai_basis[k - 1][i] -= r * ai_basis[l - 1][i]
                    for j in range(1, l):
                        ind_k = find_full_index(mu, k, j)
                        ind_l = find_full_index(mu, l, j)
                        mu[ind_k][1] -= r * mu[ind_l][1]
                    ind = find_full_index(mu, k, l)
                    mu[ind][1] -= r
            k += 1
        if k <= n:
            continue
        return ai_basis


def test_LLL():
    a1 = [1, 8, 12, 1, 4]
    a2 = [6, -6, 1, 14, 2]
    a3 = [5, 6, 7, 1, 2]
    a4 = [12, -1, 5, 1, 9]
    A = list()
    A.append(a1)
    A.append(a2)
    A.append(a3)
    A.append(a4)
    print("Matrix")
    print_matrix(A)
    print("LLL")
    A = LLL_algh(A)
    print_matrix(A)


def generate_key(n):
    b = list()
    b.append(randint(1, 2 ** 32))
    for i in range(0, n - 1):
        val = randint(1, 2 ** 32) + sum(b)
        b.append(val)
    u = randint(1, 2 ** 32) + sum(b)
    v = randint(2, u)
    while True:
        if gcd(u, v) == 1:
            break
        v = randint(2, u)
    sigma = list()
    for i in range(0, n):
        sigma.append(i)
    shuffle(sigma)
    a = list()
    for i in range(0, n):
        val = v * b[sigma.index(i)] % u
        a.append(val)
    open_key = a
    close_key = tuple([sigma, v, u, b])
    return open_key, close_key


def cryptoanalize(a, S):
    n = len(a)
    m = int(ceil((1 / 2) * (n ** (1/2))))
    c = list()
    for i in range(0, n):
        c_i = list()
        for j in range(0, n):
            if i == j:
                c_i.append(1)
            else:
                c_i.append(0)
        c_i.append(m * a[i])
        c.append(c_i)
    c_n = list()
    for i in range(0, n):
        c_n.append(1 / 2)
    c_n.append(m * S)
    c.append(c_n)
    print("Matrix")
    print_matrix(c)
    B = LLL_algh(c)
    print("-----------------")
    print("LLL-matrix")
    print_matrix(B)
    i = 0
    print("-----------------")
    print("Result:")
    for b in B:
        if b[len(b) - 1] == 0 and abs(b[i]) == 1 / 2:
            x_i_pl = list()
            x_i_mn = list()
            res_pl = list()
            res_mn = list()
            for j in range(0, n):
                x_i_mn.append(-b[j] + 1 / 2)
                x_i_pl.append(b[j] + 1 / 2)
            for j in range(0, n):
                res_pl.append(x_i_pl[j] * a[j])
                res_mn.append(x_i_mn[j] * a[j])
            if sum(res_pl) == S:
                return list(map(lambda x: int(x), x_i_pl))
            elif sum(res_mn) == S:
                return list(map(lambda x: int(x), x_i_mn))
        i += 1
    return 0


def encrypt(open_key, X):
    Y = 0
    for i in range(0, len(X)):
        Y += open_key[i] * X[i]
    print(Y)
    return Y

def main():
    # var2 constants
    S = 5500
    A = [2623, 395, 35, 205, 3265, 55, 815, 95, 1655, 1304]
    ai_basis = [10, 15, 17]
   # LLL_algh(ai_basis)
    #print(ai_basis)
    # open_key, close_key = generate_key(10)
    open_key = [1148139072373, 1549926979992, 1332848016239, 131153880541, 321298864000, 2162694097211, 1737738292645, 1129160628101, 1634656014996, 1297638970676]
    close_key = ([7, 8, 3, 1, 0, 9, 4, 6, 5, 2], 436434491491, 2282812819458, [2538819365, 3905006220, 10275505357, 16985762388, 35226172069, 72397612136, 141749483998, 286294868611, 570687832283, 1142691010787])
    #X = [0, 1, 1, 1, 0, 1, 1, 1, 0, 1]
    #encrypt(open_key, X)
    print(cryptoanalize(A, S))
    x = cryptoanalize(A, S)
    y = 0
    for i in range(len(A)):
        y += A[i] * x[i]
    print(y)


#test_LLL()
main()