from random import randrange, getrandbits, random
def is_prime(n, k=128):
    """ Test if a number is prime
        Args:
            n -- int -- the number to test
            k -- int -- the number of tests to do
        return True if n is prime
    """
    # Test if n is not even.
    # But care, 2 is prime !
    if n == 2 or n == 3:
        return True
    if n <= 1 or n % 2 == 0:
        return False
    # find r and s
    s = 0
    r = n - 1
    while r & 1 == 0:
        s += 1
        r //= 2
    # do k tests
    for _ in range(k):
        a = randrange(2, n - 1)
        x = pow(a, r, n)
        if x != 1 and x != n - 1:
            j = 1
            while j < s and x != n - 1:
                x = pow(x, 2, n)
                if x == 1:
                    return False
                j += 1
            if x != n - 1:
                return False
    return True


def generate_prime_candidate(length):
    """ Generate an odd integer randomly
        Args:
            length -- int -- the length of the number to generate, in bits
        return a integer
    """
    # generate random bits
    p = getrandbits(length)
    # apply a mask to set MSB and LSB to 1
    p |= (1 << length - 1) | 1
    return p
def generate_prime_number(length=1024):
    """ Generate a prime
        Args:
            length -- int -- length of the prime to generate, in          bits
        return a prime
    """
    p = 4
    # keep generating while the primality test fail
    while not is_prime(p, 128):
        p = generate_prime_candidate(length)
    return p

'''
for i in range(10000):
    if len(str(generate_prime_candidate(i+1))) >= 50:
        print()
        break
'''


def AE(A, B):
    r1 = B
    r2 = A

    rs = [B, A]
    qs = []


    while rs[-1] != 0:
        qs.append(rs[-2] // rs[-1])
        rs.append(rs[-2] % rs[-1])

    return rs[-2]

def find_D(fi):

    out = 1 * fi // 5

    for i in range(fi-out):
        if AE(fi-i-out, fi) == 1:
            return fi-i-out



def find_E(A, B):
    r1 = B
    r2 = A

    rs = [B, A]
    qs = []

    Kj = [0, 1]

    while rs[-1] != 0:
        qs.append(rs[-2] // rs[-1])
        rs.append(rs[-2] % rs[-1])

        Kj.append(qs[-1] * Kj[-1] + Kj[-2])

    idx = len(Kj -4)

    # print(rs, qs)
    return Kj[-2]

l = [' ', 'а', 'б', 'в', 'г', 'д', 'е', 'ж', 'з', 'и', 'й', 'к', 'л', 'м', 'н', 'о', 'п', 'р', 'с', 'т', 'у', 'ф', 'х', 'ц', 'ч', 'ш', 'щ', 'ъ', 'ы', 'ь', 'э', 'ю', 'я']
def get_code(c):
    ret = l.index(c)
    if ret < 10:
        return '0' + str(ret)
    else:
        return str(ret)


def encode(s):

    return int(''.join([get_code(c) for c in s]))

def gen_keys(byte_len):
    p1 = generate_prime_number(byte_len)
    p2 = generate_prime_number(byte_len)
    M = p1 * p2

    print('p1:', p1)
    print('p2:', p2)
    print('M', M)
    print('M len:', len(str(p1*p2)))

    fi = (p1 - 1) * (p2 - 1)
    print('fi: ', fi)

    D = find_D(fi)
    E = find_E(D, fi)


    print('D: ', D)
    print('E: ', E)

    return M, D, E


# Mm = 4077599079861103062161070927516158477409733157845537591441632356483314364489065340039377643553910891
# Em = 25092117
# Dm = 255371695852971190389720158260140526611529770329545078278739763160868458300098713710098088454270781

M, D, E = gen_keys(5)
Mm, Dm, Em = gen_keys(5)


msg = encode('тест тест тест тест тест')
msg = 17
print('msg: ', msg)


s = pow(msg, D, M)
c = pow(s, Em, Mm)
a= pow(c,Dm ,Mm)
x = pow(a, E, M)

alt_c = pow(msg, Em, Mm)
alt_s = pow(alt_c, D, M)
alt_a= pow(alt_s,E,M)
alt_x = pow(alt_a, Dm, Mm)


# print(c)
# print(s)
# print(a)
print('encoded msg: ', x)
print('alt encoded msg: ', alt_x)