from fractions import gcd
import string

alphabet = string.ascii_uppercase

def bin2str(num):
    return "{0:b}".format(num)

def factor(n):
    a = 2
    j = 2
    B = 73

    while j<=B:
        a = pow(a,j) % n
        d = gcd(a-1, n)
        if 1 < d and d < n:
            return d

        j+=1

    return -1

def phi(n):
    nfac = factor(n)
    print(nfac)
    nfac2 = n/nfac
    return (nfac-1)*(nfac2-1)

def text_to_int(text):
    text = text.upper()
    n = len(text)
    result = 0

    for i in range(n):
        result += alphabet.index(text[i])*pow(26, n-i-1)

    return result

def int_to_text(number):
    remainders = []
    while number != 0:
        r = int(number % 26)
        remainders.insert(0, r)
        number = number//26

    text = ""
    for j in remainders:
        text += alphabet[j]
    return text

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def quadmult(x, b, n):
    z = 1
    b = bin2str(int(b))[::-1]

    for i in range((len(b)-1),-1,-1):
        z = pow(z,2) % n
        print(i)
        if b[i] == "1":
            z = (z*x) % n

    return z

def rsa_dec(text, n, b):
    dec_numbers = []
    phi_n = phi(n)
    a = modinv(b, phi_n)
    print(a)
    dec_text = ""

    for i in range(len(text)):
        dec_numbers.append(quadmult(text[i], a, n))
        dec_text += int_to_text(dec_numbers[i])

    return dec_text


text = [6340, 8309, 14010, 8936, 27358, 25023, 16481, 25809,
23614, 7135, 24996, 30590, 27570, 26486, 30388, 9395,
27584, 14999, 4517, 12146, 29421, 26439, 1606, 17881,
25774, 7647, 23901, 7372, 25774, 18436, 12056, 13547,
7908, 8635, 2149, 1908, 22076, 7372, 8686, 1304,
4082, 11803, 5314, 107, 7359, 22470, 7372, 22827,
15698, 30317, 4685, 14696, 30388, 8671, 29956, 15705,
1417, 26905, 25809, 28347, 26277, 7897, 20240, 21519,
12437, 1108, 27106, 18743, 24144, 10685, 25234, 30155,
23005, 8267, 9917, 7994, 9694, 2149, 10042, 27705,
15930, 29748, 8635, 23645, 11738, 24591, 20240, 27212,
27486, 9741, 2149, 29329, 2149, 5501, 14015, 30155,
18154, 22319, 27705, 20321, 23254, 13624, 3249, 5443,
2149, 16975, 16087, 14600, 27705, 19386, 7325, 26277,
19554, 23614, 7553, 4734, 8091, 23973, 14015, 107,
3183, 17347, 25234, 4595, 21498, 6360, 19837, 8463,
6000, 31280, 29413, 2066, 369, 23204, 8425, 7792,
25973, 4477, 30989]

dec_text = rsa_dec(text, 31313, 4913)

print(dec_text)