def mod_exp(base, exp, mod):
    result = 1
    for _ in range(exp):
        result = (result * base) % mod
    return result

def pgdc(a, b):
    while b:
        a, b = b, a % b
    return a

def inverse_mod(e, phi):
    # cherche d tel que e * d ≡ 1 (mod phi)
    for d in range(1, phi):
        if (e * d) % phi == 1:
            return d
    raise ValueError("Pas d'inverse : e et phi ne sont pas premiers entre eux")

# Paramètres RSA simplifiés (petits nombres !)
p, q = 3, 11
n = p * q                  # module
phi = (p - 1) * (q - 1)    # indicatrice d'Euler : phi(n)

# Choix de e : 1 < e < phi et pgdc(e, phi) = 1
e = 3
assert 1 < e < phi and pgdc(e, phi) == 1, "e invalide"

# Calcul de d : inverse modulaire de e modulo phi
d = inverse_mod(e, phi)

print(f"n = {n}, phi = {phi}, e = {e}, d = {d}")

# Message = un entier < n
message = 4

# Chiffrement (avec la clé publique)
ciphertext = mod_exp(message, e, n)
print("Chiffré :", ciphertext)

# Déchiffrement (avec la clé privée)
decrypted = mod_exp(ciphertext, d, n)
print("Déchiffré :", decrypted)