import math
import random

# Take in a base 26 "word" and return english
def base26ToWords(number):
    alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    word = ""

    while number > 0:
        remainder = number % 26
        # Map the remainder to the corresponding letter in the alphabet
        word = alphabet[remainder] + word
        number //= 26

    return word
# Returns a list storing [x, y, gcd(a,b)] where ax + by = gcd(a,b).
def EEA(a,b):

    # End of algorithm, 1*a + 0*b = a
    if b == 0:
        return [1,0,a]

    # Recursive case.
    else:

        # Next quotient and remainder.
        q = a//b
        r = a%b

        # Algorithm runs on b, r.
        rec = EEA(b,r)

        # Here is how we put the solution back together!
        return [rec[1], rec[0]-q*rec[1], rec[2]]

# Returns the modular inverse of x mod n. Returns 0 if there is no modular inverse
def modInv(x,n):

    # Call the Extended Euclidean.
    arr = EEA(n, x)

    # Indicates that there is no solution.
    if arr[2] != 1:
        return 0

    # Do the wrap around, if necessary.
    if arr[1] < 0:
        arr[1] += n

    # This is the modular inverse.
    return arr[1]

def main():
    # Our two public keys
    n = 576025912082114341909169
    e = 395065083027011624330977
    # Our two primes
    p = 832176222161
    q = 692192226529
    # Just phi, one of the private keys
    phi = (p-1)*(q-1)

    # We can now solve for d since it is e^-1 mod phi(n)
    d = modInv(e, int(phi))

    # Capture the ciphertext in different blocks
    cipher = [488798928261625380184161,
              533946500611718831345802,
              411942882720703143384960,
              20068354290376977207914,
              252864055600177840617225,
              144565738643838496733483,
              98121155489099542089269,
              377474600037914621137040]

    # Loop through the blocks and apply the factorization
    for block in cipher:
        print(base26ToWords(pow(block, d, n)))

# Run it!
main()