def mod_inv(a, m):
    # Calcul de l'inverse modulaire de a modulo m avec l'algorithme d'Euclide étendu
    def egcd(a, b):
        if b == 0:
            return a, 1, 0
        else:
            g, x, y = egcd(b, a % b)
            return g, y, x - (a // b) * y
    g, x, _ = egcd(a, m)
    if g != 1:
        raise Exception('Pas d\'inverse modulaire')
    else:
        return x % m

def matrix_det_2x2(matrix):
    # Déterminant 2x2
    return matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0]

def matrix_mod_inv_2x2(matrix, modulus):
    det = matrix_det_2x2(matrix) % modulus
    det_inv = mod_inv(det, modulus)

    # Matrice adjointe (cofacteurs transposés)
    inv_matrix = [
        [matrix[1][1] * det_inv % modulus, (-matrix[0][1]) * det_inv % modulus],
        [(-matrix[1][0]) * det_inv % modulus, matrix[0][0] * det_inv % modulus]
    ]
    return inv_matrix

def text_to_numbers(text):
    return [ord(c) - ord('a') for c in text.lower()]

def numbers_to_text(numbers):
    return ''.join(chr(n + ord('a')) for n in numbers)

def hill_decrypt(ciphertext, key):
    modulus = 26
    key_numbers = text_to_numbers(key)
    key_matrix = [key_numbers[:2], key_numbers[2:]]
    inv_key_matrix = matrix_mod_inv_2x2(key_matrix, modulus)

    ciphertext_numbers = text_to_numbers(ciphertext)
    plaintext_numbers = []

    for i in range(0, len(ciphertext_numbers), 2):
        pair = ciphertext_numbers[i:i+2]
        # Multiplication matrice-vecteur modulaire
        decrypted_pair = [
            (inv_key_matrix[0][0] * pair[0] + inv_key_matrix[0][1] * pair[1]) % modulus,
            (inv_key_matrix[1][0] * pair[0] + inv_key_matrix[1][1] * pair[1]) % modulus
        ]
        plaintext_numbers.extend(decrypted_pair)

    return numbers_to_text(plaintext_numbers)

# Variables données
clef = "IJDK"
mot_de_passe_chiffre = "yzhxvq"

# Déchiffrement
message_dechiffre = hill_decrypt(mot_de_passe_chiffre, clef)
print("Message déchiffré :", message_dechiffre)