######################################################################################################
# This script can't be executed as is (some of its code was removed to support non-trivial solutions)#
######################################################################################################

import math
import random
import numpy as np
from numpy.linalg import inv

def get_coprimes(n):
    return [m for m in range(1, n) if math.gcd(m, n) == 1]

def calc_decode_matrix(n):
    theta = (2 * math.pi) / n
    primitive_root = complex(math.cos(theta), math.sin(theta))
    coprimes = np.array(get_coprimes(n), ndmin=2).transpose()
    a = np.arange(n//2)
    return primitive_root ** (coprimes * a)

def calc_encode_matrix(n):
    return inv(calc_decode_matrix(n))

def encode(text, n, scale):
    cleartext = text + text[::-1]
    encode_matrix = calc_encode_matrix(n)
    plaintext_complex = encode_matrix.dot(cleartext)
    plaintext = [round(x.real * scale) for x in plaintext_complex]
    return plaintext

def generate_secret_key(n):
    return [random.randrange(3) - 1 for i in range(n // 2)]

def decode(plaintext, n, scale):
    decode_matrix = calc_decode_matrix(n)
    cleartext_complex_scaled = decode_matrix.dot(plaintext)
    cleartext_complex = [i/scale for i in cleartext_complex_scaled]
    return cleartext_complex[:n//4]

def compute_error(n, RR):
    e = [0] * (n // 2)
    number_of_errors = int((n // 2) * error_rate)
    for i in range(number_of_errors):
        j = random.randrange(n // 2)
        if random.randrange(2) == 0:
            e[j] = -1
        else:
            e[j] = 1
    return RR(e)

def encrypt(plaintext, s, n, q, RR):
    a = RR([random.randrange(q) for i in range(n//2)])
    e = compute_error(n, RR)
    b = a*s + plaintext + e
    return a, b

def decrypt(a, b, s):
    return b-a*s

def mod_around_0(x, q):
    if x > q//2:
        return x-q
    else:
        return x

def plaintext_to_cleartext(plaintext, n, scale, q):
    plaintext_coeffs = list(plaintext)
    plaintext_coeffs = [mod_around_0(int(i), q) for i in plaintext_coeffs]
    cleartext_complex = decode(plaintext_coeffs, n, scale)
    cleartext = [i.real for i in cleartext_complex]
    return cleartext