import math
#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
# Function to decrypt ElGamal ciphertext
def elgamal_decrypt(ciphertext, p, g, x):
    c1, c2 = ciphertext
    # Compute the shared key
    shared_key = pow(c1, x, p)
    # Compute the inverse of the shared key
    inv_shared_key = modInv(shared_key, p)
    # Decrypt the ciphertext
    decrypted = (c2 * inv_shared_key) % p
    return decrypted
# 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]

# Take in the generator a base and a prime and solve the DLP to find the private expo
# We pass `g`, 'Ya', then 'q'
def bsgs(g, h, p):
    N = math.ceil(math.sqrt(p - 1))  # phi(p) is p-1 if p is prime

    # Store hashmap of g^{1...m} (mod p). Baby step.
    tbl = {pow(g, i, p): i for i in range(N)}

    # Precompute via Fermat's Little Theorem
    c = pow(g, N * (p - 2), p)

    # Search for an equivalence in the table. Giant step.
    for j in range(N):
        y = (h * pow(c, j, p)) % p
        if y in tbl:
            return j * N + tbl[y]

    # Solution not found
    return None

def main():
    # Prime
    q = 310000037
    # Primitive root
    g = 52216224
    # Alices public exponent
    Ya = 32298658
    # Run the 'Baby Step, Giant Step' algorithm to solve for Xa
    # We pass `g`, 'Ya', then 'q'
    private_key = bsgs(g,Ya,q)

    # Store the ciphertext as a list of tuples
    ciphertext = [
(56495539, 72767212),(62083516, 76971521),(181398440, 263421160),
(149867850, 72743477),(14826439, 190288780),(113953407, 197793189),
(117331466, 185360595),(291767686, 140312582),(97578813, 288144131),
(66782213, 277003739),(189849901, 192777619),(147582903, 21503450),
(154299245, 242826784),(86211909, 200694188),(31309028, 293758361),
(21217580, 3535169),(79019712, 49185229),(213930082, 159557439),
(73624006, 229408211),(292736574, 18644176),(237123292, 168250610),
(38995570, 306955959),(199390530, 176530325),(226189829 ,196581913),
(195038651 ,170658203)]

    # Display the decrypted message
    for tuple in ciphertext:
        print(base26ToWords(elgamal_decrypt(tuple, q, g, private_key)))
# Run it!
main()