modcalc.py

def sep(title=None):
    if title:
        print("--- {} ---".format(title))
    else:
        print("-" * 38)

def show_divisions(divs):
    for (A, B, q, r) in divs:
        print("{} = {}*{} + {}".format(A, q, B, r))

def _expr_to_string(expr, R):
    terms = []
    for i in range(len(R)):
        c = expr.get(i, 0)
        if c != 0:
            terms.append("{}*{}".format(c, R[i]))
    if not terms:
        return "0"
    return " + ".join(terms)

def _rjust(val, w):
    s = str(val)
    L = len(s)
    if L < w:
        return " " * (w - L) + s
    return s

def _col_width(values):
    w = 1
    for v in values:
        l = len(str(v))
        if l > w:
            w = l
    return w + 1

def _print_table(header_vals, row_vals, cell_fn, title):
    sep(title)
    candidates = list(header_vals) + list(row_vals)
    for i in row_vals:
        for j in header_vals:
            candidates.append(cell_fn(i, j))
    w = _col_width(candidates)

    first_cell = " " * w + "|"
    print(first_cell, end="")
    for j in header_vals:
        print(_rjust(j, w), end="")
    print()

    print("-" * (w + 1 + w * len(header_vals)))

    for i in row_vals:
        print(_rjust(i, w) + "|", end="")
        for j in header_vals:
            v = cell_fn(i, j)
            print(_rjust(v, w), end="")
        print()

def gcd(a, b):
    a = abs(a); b = abs(b)
    while b:
        a, b = b, a % b
    return a

def _format_factorization(fdict):
    parts = []
    for p in sorted(fdict.keys()):
        e = fdict[p]
        if e == 1:
            parts.append(str(p))
        else:
            parts.append("{}^{}".format(p, e))
    return " * ".join(parts) if parts else "1"

def prime_factors_ladder(n):
    if n == 0:
        print("0 : factorisation non définie (multiple de tous les entiers).")
        return {}
    sign = -1 if n < 0 else 1
    if sign < 0:
        print("Attention: n < 0 -> on factorise |n| et on garde le signe -1.")
    n = abs(n)
    if n == 1:
        print("1")
        return {}

    print(n)
    f = {}

    while n % 2 == 0:
        n //= 2
        print("{} | {}".format(n, 2))
        f[2] = f.get(2, 0) + 1

    p = 3
    while p * p <= n:
        while n % p == 0:
            n //= p
            print("{} | {}".format(n, p))
            f[p] = f.get(p, 0) + 1
        p += 2

    if n > 1:
        print("1 | {}".format(n))
        f[n] = f.get(n, 0) + 1

    return f if sign > 0 else ({-1:1} | f) if hasattr(dict, "__or__") else (dict([(-1,1)]) | f)

def egcd_verbose(a, b, show=True, show_back=True):
    A0, B0 = a, b
    divs = []
    R = [a, b]
    Q = [None, None]

    old_r, r = a, b
    old_s, s = 1, 0
    old_t, t = 0, 1

    while r != 0:
        q = old_r // r
        rem = old_r - q * r
        divs.append((old_r, r, q, rem))
        R.append(rem)
        Q.append(q)
        old_r, r = r, rem
        old_s, s = s, old_s - q * s
        old_t, t = t, old_t - q * t

    g, x, y = old_r, old_s, old_t
    k = len(R) - 2

    if show:
        sep("Algorithme d'Euclide ({} , {})".format(A0, B0))
        show_divisions(divs)
        print("pgcd({}, {}) = {}".format(A0, B0, g))

    if show and show_back and k >= 2:
        sep("Remontée (combinaison linéaire)")
        print("{} = {} - {}*{}".format(R[k], R[k-2], Q[k], R[k-1]))
        expr = {k-2: 1, k-1: -Q[k]}
        for j in range(k-1, 1, -1):
            cj = expr.get(j, 0)
            if cj == 0:
                continue
            print("Remplacer {} par {} - {}*{}".format(R[j], R[j-2], Q[j], R[j-1]))
            expr.pop(j, None)
            expr[j-2] = expr.get(j-2, 0) + cj
            expr[j-1] = expr.get(j-1, 0) - cj * Q[j]
            print("=> {} = {}".format(R[k], _expr_to_string(expr, R)))
        x_back = expr.get(0, 0)
        y_back = expr.get(1, 0)
        print("Donc {} = {}*{} + {}*{}".format(g, x_back, A0, y_back, B0))

    if show:
        print("Coeffs de Bézout : x = {}, y = {}".format(x, y))
        print("Vérif : {}*{} + {}*{} = {}".format(A0, x, B0, y, A0*x + B0*y))
    return g, x, y

def inv_mod(a, m, show=True):
    if m <= 0:
        if show:
            print("Le module doit être > 0")
        return False, None
    g, x, y = egcd_verbose(a, m, show=show, show_back=True)
    if g != 1:
        if show:
            sep("Inverse modulaire")
            print("gcd({}, {}) = {} ≠ 1 : pas d'inverse modulo {}.".format(a, m, g, m))
        return False, None
    inv = x % m
    if show:
        sep("Inverse mod {}".format(m))
        print("Inverse trouvé : {}^(-1) ≡ {}  [ {} ]".format(a, inv, m))
        print("Vérif : ({}*{}) % {} = {}".format(a, inv, m, (a*inv) % m))
    return True, inv

def solve_congruence(a, b, m, show=True, list_rep=True):
    if m <= 0:
        if show:
            print("Le module doit être > 0")
        return False, None, None, None
    sep("Résolution de {} x ≡ {}  [ {} ]".format(a, b, m))
    d, xg, yg = egcd_verbose(a, m, show=True, show_back=False)
    if b % d != 0:
        print("Comme {} ne divise pas {}, aucune solution.".format(d, b))
        return False, None, None, d
    a1 = a // d; b1 = b // d; m1 = m // d
    print("On réduit : a'={}, b'={}, m'={} (d = {})".format(a1, b1, m1, d))
    print("Nouvelle équation : {} x ≡ {}  [ {} ]".format(a1, b1, m1))
    ok, inv = inv_mod(a1, m1, show=True)
    if not ok:
        print("Problème inattendu : a' et m' ne sont pas copremiers.")
        return False, None, None, d
    x0 = (inv * b1) % m1
    sep("Solution")
    print("Solution de base : x0 ≡ {} * {} ≡ {}  [ {} ]".format(inv, b1, x0, m1))
    print("Vérif : ({}*{}) % {} = {}  (doit ≡ {})".format(a, x0, m, (a*x0) % m, b % m))
    print("Forme générale des solutions : x ≡ {}  [ {} ]".format(x0, m1))
    if d > 1:
        k_values = ", ".join(str(i) for i in range(d))
        print("Remontée au mod {} : x ≡ {} + {}k, k = {}.".format(m, x0, m1, k_values))
        reps = []
        for k in range(d):
            reps.append((x0 + k*m1) % m)
        reps = sorted(list(set(reps)))
        if list_rep:
            print("Représentants (mod {}): {}".format(m, ", ".join(str(r) for r in reps)))
    return True, x0, m1, d

def solve_ax_plus_c_eq_b(a, c, b, m):
    sep("0) Mise en forme / réduction modulo {}".format(m))
    if (b % m) == 0 and (c % m) != 0:
        print("{} x ≡ -{} ≡ {}  [ {} ]".format(a, c, (-c) % m, m))
    elif (c % m) == 0:
        print("{} x ≡ {}  [ {} ]".format(a, b % m, m))
    else:
        print("{} x ≡ {} - {} ≡ {}  [ {} ]".format(a, b % m, c % m, (b - c) % m, m))
    return solve_congruence(a, (b - c) % m, m, show=True, list_rep=True)

def solve_x_plus_c_eq_b(c, b, m):
    sep("0) Mise en forme / réduction modulo {}".format(m))
    print("{} ≡ {}  [ {} ]".format(c, c % m, m))
    print("{} ≡ {}  [ {} ]".format(b, b % m, m))
    print("=> x ≡ {}  [ {} ]".format((b - c) % m, m))
    return solve_congruence(1, (b - c) % m, m, show=True, list_rep=True)

def equations_menu_option():
    sep("Équations - choisir une forme")
    print("1) a x ≡ b  [ m ]")
    print("2) a x + c ≡ 0  [ m ]")
    print("3) a x + c ≡ b  [ m ]")
    print("4) x + c ≡ b  [ m ]")
    ch = input("> Choix forme : ").strip()

    try:
        if ch == "1":
            a = int(input("a = "))
            b = int(input("b = "))
            m = int(input("m (module > 0) = "))
            solve_congruence(a, b, m, show=True, list_rep=True)

        elif ch == "2":
            a = int(input("a = "))
            c = int(input("c = "))
            m = int(input("m (module > 0) = "))
            sep("Équation {}x + {} = 0  [ {} ]".format(a, c, m))
            print("Réécriture : {}x ≡ -{} ≡ {}  [ {} ]".format(a, c, (-c) % m, m))
            solve_congruence(a, (-c) % m, m, show=True, list_rep=True)

        elif ch == "3":
            a = int(input("a = "))
            c = int(input("c = "))
            b = int(input("b = "))
            m = int(input("m (module > 0) = "))
            solve_ax_plus_c_eq_b(a, c, b, m)

        elif ch == "4":
            c = int(input("c = "))
            b = int(input("b = "))
            m = int(input("m (module > 0) = "))
            solve_x_plus_c_eq_b(c, b, m)

        else:
            print("Choix inconnu.")
    except:
        print("Entrée invalide.")

def table_Z(start, end, op):
    if start > end:
        start, end = end, start
    rows = list(range(start, end + 1))
    cols = list(range(start, end + 1))
    if op == "+":
        cell = lambda i, j: i + j
        title = "Table d'addition en Z, [{}..{}]".format(start, end)
    else:
        cell = lambda i, j: i * j
        title = "Table de multiplication en Z, [{}..{}]".format(start, end)
    _print_table(cols, rows, cell, title)

def table_Zn(n, op):
    if n <= 0:
        print("Le module n doit être > 0")
        return
    rows = list(range(0, n))
    cols = list(range(0, n))
    if op == "+":
        cell = lambda i, j: (i + j) % n
        title = "Table d'addition modulo {}".format(n)
    else:
        cell = lambda i, j: (i * j) % n
        title = "Table de multiplication modulo {}".format(n)
    _print_table(cols, rows, cell, title)

    Zn_list = [i for i in range(n)]
    print("\nZ_{} = {{ {} }}".format(n, ", ".join([str(x) for x in Zn_list])))
    Zn_star = [a for a in range(n) if gcd(a, n) == 1]
    print("Z_{}* = {{ {} }}".format(n, ", ".join([str(x) for x in Zn_star])))

def solve_system_crt_coprime():
    sep("CRT (formule directe)")
    k = int(input("Nombre d'équations k = "))
    if k <= 0:
        print("k doit être >= 1")
        return

    residues = []
    moduli = []
    for i in range(1, k+1):
        print("Equation #{} :".format(i))
        ai = int(input("  a{} = ".format(i)))
        mi = int(input("  m{} (>0) = ".format(i)))
        if mi <= 0:
            print("Module > 0 requis.")
            return
        ai = ai % mi
        residues.append(ai)
        moduli.append(mi)

    for i in range(k):
        for j in range(i+1, k):
            if gcd(moduli[i], moduli[j]) != 1:
                print("Moduli NON copremiers (m{}={}, m{}={}).".format(i+1, moduli[i], j+1, moduli[j]))
                print("Utilise l'option (6) Système modulaire (cas général).")
                return

    print("Système :")
    for i in range(k):
        print("x ≡ {}  [ {} ]".format(residues[i], moduli[i]))

    M = 1
    for mi in moduli:
        M *= mi
    sep("Produit total")
    prod_str = " * ".join(str(mi) for mi in moduli)
    print("M = {} = {}".format(prod_str, M))

    sep("Sous-produits")
    Mi_list = []
    for i in range(k):
        Mi = M // moduli[i]
        Mi_list.append(Mi)
        print("M{} = M / m{} = {}".format(i+1, i+1, Mi))

    sep("Recherche des inverses (Mi * yi ≡ 1 [mi])")
    yi_list = []
    for i in range(k):
        Mi = Mi_list[i]
        mi = moduli[i]
        r = Mi % mi
        ok, yi = inv_mod(Mi, mi, show=False)
        if not ok:
            print("Impossible de trouver l'inverse de {} modulo {} (devrait être possible ici).".format(Mi, mi))
            return
        yi_list.append(yi)
        print("{}*y{} ≡ 1 [{}] -> {} ≡ {} [{}] -> y{} ≡ {} [{}] => y{} = {}".format(
            Mi, i+1, mi, Mi, r, mi, i+1, yi, mi, i+1, yi
        ))

    sep("Construction (formule CRT)")
    terms_str = "  +  ".join("{} * {} * {}".format(residues[i], Mi_list[i], yi_list[i]) for i in range(k))
    print("x ≡ {}  [ {} ]".format(terms_str, M))

    sep("Calcul des termes")
    terms = []
    for i in range(k):
        t = residues[i] * Mi_list[i] * yi_list[i]
        terms.append(t)
        print("Terme #{} = {}*{}*{} = {}".format(i+1, residues[i], Mi_list[i], yi_list[i], t))

    sep("Somme")
    S = sum(terms)
    print("S = {}".format(" + ".join(str(t) for t in terms)), end="")
    print(" = {}".format(S))
    sep("Réduction")
    x0 = S % M
    print("x0 = {} % {} = {}".format(S, M, x0))

    sep("Solution canonique")
    print("x ≡ {}  [ {} ]".format(x0, M))

    sep("Vérifications")
    for i in range(k):
        mi = moduli[i]
        ai = residues[i]
        print("{} % {} = {}  (attendu {}){}".format(
            x0, mi, x0 % mi, ai, "  (ok)" if (x0 % mi) == ai else "  (!!)"
        ))

    sep("Forme générale")
    print("x = {} + {}*k,  k entier".format(x0, M))

def pow_mod_verbose(a, e, m):
    sep('Puissance mod m - méthode "décomposition binaire"')

    if m <= 0:
        print("Le module doit être > 0")
        return
    if e < 0:
        print("Exposant négatif non pris en charge.")
        return
    if e == 0:
        print("Objectif : calculer {}^0  [{}]".format(a, m))
        print("{}^0 ≡ 1  [{}]".format(a, m))
        sep("Résultat")
        print("{}^{} (mod {}) = {}".format(a, e, m, 1 % m))
        return

    print("a = {}".format(a))
    print("e = {}".format(e))
    print("m = {}".format(m))
    print("\nObjectif : calculer {}^{}  [{}]".format(a, e, m))

    orig_e = e
    is_prime = True
    if m < 2:
        is_prime = False
    else:
        d = 2
        while d * d <= m:
            if m % d == 0:
                is_prime = False
                break
            d += 1

    if is_prime and gcd(a, m) == 1 and e >= (m - 1):
        sep("Réduction de l'exposant (th. de Fermat)")
        print("m = {} est premier et gcd({}, {}) = 1.".format(m, a, m))
        print("On sait : {}^({}-1) ≡ 1  [ {} ]".format(a, m, m))
        r = e % (m - 1)
        q = e // (m - 1)
        print("On écrit e = q*({}-1) + r avec e = {} :".format(m, orig_e))
        print("{} = {} * {} + {}.".format(orig_e, q, m - 1, r))
        print("Donc {}^{} ≡ {}^{}  [ {} ]".format(a, orig_e, a, r, m))
        e = r
        if e == 0:
            sep("Résultat")
            print("{}^{} (mod {}) = 1".format(a, orig_e, m))
            print("(Car l'exposant est multiple de {}-1 et {}^({}-1) ≡ 1 [ {} ])".format(m, a, m, m))
            return

    def small_rep(x, mod):
        return str(x % mod)

    def power2_repr(a_sym, k):
        if k == 0:
            return "{}".format(a_sym)
        s = "({}^2)".format(a_sym)
        for _ in range(1, k):
            s = "({}^2)".format(s)
        return s

    bits = []
    k = 0
    t = e
    while t > 0:
        if (t & 1) == 1:
            bits.append(k)
        t >>= 1
        k += 1
    bits_desc = sorted(bits, reverse=True)

    somme_num = " + ".join(str(1 << k) for k in bits_desc)
    somme_pow2 = " + ".join("2^{}".format(k) for k in bits_desc)
    print("\n1) Écriture de l'exposant en base 2")
    print("{} = {} = {}".format(e, somme_num, somme_pow2))

    print("\n2) Décomposition de la puissance")
    droite_pow2 = " + ".join("2^{}".format(k) for k in bits_desc)
    print("{}^{} = {}^({})".format(a, e, a, droite_pow2))
    print("     = " + " * ".join("{}^(2^{})".format(a, k) for k in bits_desc))

    print("\n3) Calculs modulo {} (paliers)".format(m))
    pow_values = {}

    val = a % m
    pow_values[0] = val
    print("- {}^1 ≡ {}  [ {} ]".format(a, small_rep(a, m), m))

    max_k = bits_desc[0] if bits_desc else 0
    prev_val = val
    for kk in range(1, max_k + 1):
        raw_sq = prev_val * prev_val
        new_val = raw_sq % m
        exp_prev = 1 << (kk - 1)
        exp_cur = 1 << kk
        print("- {}^{} = ({}^{})^2  =>  ({}^2) ≡ {}  [ {} ]".format(
            a,
            exp_cur,
            a,
            exp_prev,
            small_rep(prev_val, m),
            small_rep(new_val, m),
            m
        ))
        pow_values[kk] = new_val
        prev_val = new_val

    print("\n4) Assemblage des facteurs utiles ({})".format(", ".join("2^{}".format(k) for k in bits_desc)))
    print("{}^{} ≡ {}  [ {} ]".format(
        a, e, " * ".join("{}^(2^{})".format(a, k) for k in bits_desc), m
    ))
    factors_str = " * ".join(small_rep(pow_values[k], m) for k in bits_desc)
    print("     ≡ {}  [ {} ]".format(factors_str, m))

    acc = 1 % m
    if bits_desc:
        acc = pow_values[bits_desc[0]] % m
        print("     -> {} (premier facteur)".format(small_rep(acc, m)))
        for kk in bits_desc[1:]:
            before = acc
            acc = (acc * pow_values[kk]) % m
            print("     -> ({} * {}) % {} = {}".format(
                small_rep(before, m),
                small_rep(pow_values[kk], m),
                m,
                small_rep(acc, m)
            ))

    sep("Résultat")
    print("{}^{} (mod {}) = {}".format(a, orig_e, m, acc))
    print("(Vérif rapide : {} % {} = {})".format(acc, m, acc % m))

def show_factorization_and_option_gcd():
    sep("Décomp. facteurs premiers")
    k = int(input("Nombre d'entiers (1 ou 2) = "))
    if k not in (1, 2):
        print("Choix invalide (1 ou 2).")
        return

    n1 = int(input("n1 = "))
    sep("n1 : échelle")
    f1 = prime_factors_ladder(n1)
    absn1 = abs(n1)
    print("{} = {}".format(n1, _format_factorization({p:e for p,e in f1.items() if p != -1} if -1 in f1 else f1)))

    if k == 1:
        return

    n2 = int(input("n2 = "))
    sep("n2 : échelle")
    f2 = prime_factors_ladder(n2)
    print("{} = {}".format(n2, _format_factorization({p:e for p,e in f2.items() if p != -1} if -1 in f2 else f2)))

    sep("PGCD par facteurs")
    f1pos = {p:e for p,e in f1.items() if p > 1}
    f2pos = {p:e for p,e in f2.items() if p > 1}
    common = {}
    for p in f1pos:
        if p in f2pos:
            common[p] = min(f1pos[p], f2pos[p])

    pgcd_val = 1
    for p, e in common.items():
        v = 1
        for _ in range(e):
            v *= p
        pgcd_val *= v

    if common:
        fact_str = _format_factorization(common)
        print("PGCD({}, {}) = {} = {}".format(n1, n2, fact_str, pgcd_val))
    else:
        print("PGCD({}, {}) = 1".format(n1, n2))

def run_pgcd_bezout():
    sep("PGCD / Bézout")
    try:
        a = int(input("a = "))
        b = int(input("b = "))
        egcd_verbose(a, b, show=True, show_back=True)
    except:
        print("Entrée invalide.")

def run_inverse():
    sep("Inverse mod m")
    try:
        a = int(input("a = "))
        m = int(input("m (module > 0) = "))
        inv_mod(a, m, show=True)
    except:
        print("Entrée invalide.")

def run_tables():
    sep("Tables (Z / Z_n)")
    try:
        print("Espace ?")
        print("  1 = Z (entiers)")
        print("  2 = Z_n (modulo n)")
        space = input("> Choix espace : ").strip()

        print("Opération ?")
        print("  1 = addition")
        print("  2 = multiplication")
        print("  3 = les deux")
        op_ch = input("> Choix opération : ").strip()

        def do_ops(do_add, do_mul, in_Z, in_Zn):
            if in_Z:
                print("Intervalle en Z :")
                s = int(input("  début = "))
                e = int(input("  fin   = "))
                if do_add: table_Z(s, e, "+")
                if do_mul: table_Z(s, e, "*")
            else:
                n = int(input("Module n (>0) : "))
                if do_add: table_Zn(n, "+")
                if do_mul: table_Zn(n, "*")

        do_add = (op_ch == "1" or op_ch == "3")
        do_mul = (op_ch == "2" or op_ch == "3")

        if space == "1":
            do_ops(do_add, do_mul, True, False)
        elif space == "2":
            do_ops(do_add, do_mul, False, True)
        else:
            print("Choix d'espace invalide.")
    except:
        print("Entrée invalide.")

def run_pow_mod():
    sep("Puissance mod m")
    try:
        a = int(input("a = "))
        e = int(input("e (exposant) = "))
        m = int(input("m (module > 0) = "))
        pow_mod_verbose(a, e, m)
    except:
        print("Entrée invalide.")

def _mod_pow_fast(a, e, m):
    if m <= 0:
        return 0
    a %= m
    res = 1 % m
    while e > 0:
        if e & 1:
            res = (res * a) % m
        a = (a * a) % m
        e >>= 1
    return res

def _inv_mod_quick(a, m):
    if m <= 0:
        return False, None
    g, x, y = egcd_verbose(a, m, show=False, show_back=False)
    if g != 1:
        return False, None
    return True, x % m

def eds_rsa_menu():
    try:
        sep("EDS RSA - paramètres")
        print("Alice : pA, qA, eA")
        pA = int(input("pA = "))
        qA = int(input("qA = "))
        eA = int(input("eA = "))
        print("Bob : pB, qB, eB")
        pB = int(input("pB = "))
        qB = int(input("qB = "))
        eB = int(input("eB = "))
        M = int(input("M (message pour chiffrement) = "))
        m = int(input("m (message à chiffrer+signer) = "))
    except:
        print("Entrée invalide.")
        return

    sep("EDS RSA - choix")
    print("1) Calcul des clés (n, phi, d) (résultats uniquement)")
    print("2) Chiffrer M pour Bob : C(M)")
    print("3) Chiffrer m pour Bob + signer C(m) avec Alice")
    print("4) Déchiffrer + vérifier signature (sur m)")
    print("5) Tout (RSA)")
    print("6) Retour")
    ch = input("> Choix : ").strip()
    if ch not in ("1","2","3","4","5"):
        return

    nA = pA * qA
    phiA = (pA - 1) * (qA - 1)
    okA, dA = _inv_mod_quick(eA, phiA)

    nB = pB * qB
    phiB = (pB - 1) * (qB - 1)
    okB, dB = _inv_mod_quick(eB, phiB)

    if (ch in ("1","5")):
        sep("RSA - Résultats clés")
        print("Alice : nA = {}, phiA = {}".format(nA, phiA))
        if okA:
            print("Alice : dA = {}".format(dA))
        else:
            print("Alice : dA n'existe pas (eA et phiA non copremiers)")
        print("Bob   : nB = {}, phiB = {}".format(nB, phiB))
        if okB:
            print("Bob   : dB = {}".format(dB))
        else:
            print("Bob   : dB n'existe pas (eB et phiB non copremiers)")
        print("Si tu veux les étapes de d : va Menu (3) Inverse mod m, avec a=e et m=phi.")

    if not okA or not okB:
        if ch != "1":
            sep("Erreur RSA")
            print("Impossible de continuer : e et phi(n) doivent être copremiers pour avoir d.")
        return

    if (ch in ("2","5")):
        sep("RSA - Chiffrement de M pour Bob")
        C_M = _mod_pow_fast(M, eB, nB)
        print("C(M) = M^eB mod nB = {}".format(C_M))
        print("Si tu veux les étapes : va Menu (7) Puissance mod m (a=M, e=eB, m=nB).")

    if (ch in ("3","5")):
        sep("RSA - Chiffrement de m + signature (sur C(m))")
        Cm = _mod_pow_fast(m, eB, nB)
        sigma = _mod_pow_fast(Cm, dA, nA)
        print("C(m) = m^eB mod nB = {}".format(Cm))
        print("sigma = C(m)^dA mod nA = {}".format(sigma))
        print("Étapes puissance : Menu (7). Étapes inverse dA : Menu (3).")

    if (ch in ("4","5")):
        sep("RSA - Réception (m) : déchiffrement + vérification")
        Cm = _mod_pow_fast(m, eB, nB)
        sigma = _mod_pow_fast(Cm, dA, nA)

        m_back = _mod_pow_fast(Cm, dB, nB)
        v = _mod_pow_fast(sigma, eA, nA)

        print("Déchiffrement : m' = C(m)^dB mod nB = {}".format(m_back))
        print("Vérif : v = sigma^eA mod nA = {}".format(v))
        print("Attendu : C(m) mod nA = {}".format(Cm % nA))
        if v == (Cm % nA):
            print("Conclusion : signature VALIDE")
        else:
            print("Conclusion : signature INVALIDE")
        print("Étapes puissance : Menu (7).")

def eds_elgamal_menu():
    try:
        sep("EDS ElGamal - paramètres")
        p = int(input("p (premier) = "))
        g = int(input("g = "))
        M = int(input("M (message) = "))
        a = int(input("a (privée Alice) = "))
        b = int(input("b (privée Bob)   = "))
        k = int(input("k (signature)    = "))
    except:
        print("Entrée invalide.")
        return

    sep("EDS ElGamal - choix")
    print("1) Chiffrement (C1,C2)")
    print("2) Déchiffrement (à partir de C1,C2)")
    print("3) Signature (r,s)")
    print("4) Vérification signature (r,s)")
    print("5) Tout (ElGamal)")
    print("6) Retour")
    ch = input("> Choix : ").strip()
    if ch not in ("1","2","3","4","5"):
        return

    yB = _mod_pow_fast(g, b, p)

    if ch in ("1","5"):
        sep("ElGamal - Chiffrement")
        C1 = _mod_pow_fast(g, a, p)
        s = _mod_pow_fast(yB, a, p)
        C2 = (M * s) % p
        print("yB = g^b mod p = {}".format(yB))
        print("C1 = g^a mod p = {}".format(C1))
        print("s  = yB^a mod p = {}".format(s))
        print("C2 = M*s mod p = {}".format(C2))
        print("Chiffré : (C1,C2)=({}, {})".format(C1, C2))
        print("Étapes puissance : Menu (7). Étapes inverse : Menu (3).")

    if ch in ("2","5"):
        sep("ElGamal - Déchiffrement")
        C1 = int(input("C1 = "))
        C2 = int(input("C2 = "))
        s = _mod_pow_fast(C1, b, p)
        ok, s_inv = _inv_mod_quick(s, p)
        print("s = C1^b mod p = {}".format(s))
        if not ok:
            print("Pas d'inverse de s modulo p.")
            print("Si tu veux les étapes : Menu (3) avec a=s, m=p.")
            return
        M_back = (C2 * s_inv) % p
        print("s^-1 mod p = {}".format(s_inv))
        print("M = C2*s^-1 mod p = {}".format(M_back))
        print("Étapes puissance : Menu (7). Étapes inverse : Menu (3).")

    if ch in ("3","5"):
        sep("ElGamal - Signature")
        pm1 = p - 1
        ok, k_inv = _inv_mod_quick(k, pm1)
        if not ok:
            print("k non inversible modulo (p-1). Choisir un autre k.")
            print("Si tu veux les étapes : Menu (3) avec a=k, m=p-1.")
            return
        r = _mod_pow_fast(g, k, p)
        s_sig = (k_inv * ((M - a * r) % pm1)) % pm1
        print("r = g^k mod p = {}".format(r))
        print("k^-1 mod (p-1) = {}".format(k_inv))
        print("s = k^-1*(M - a*r) mod (p-1) = {}".format(s_sig))
        print("Signature : (r,s)=({}, {})".format(r, s_sig))
        print("Étapes inverse : Menu (3). Étapes puissance : Menu (7).")

    if ch in ("4","5"):
        sep("ElGamal - Vérification signature")
        r = int(input("r = "))
        s_sig = int(input("s = "))
        yA = _mod_pow_fast(g, a, p)
        left = _mod_pow_fast(g, M, p)
        right = (_mod_pow_fast(yA, r, p) * _mod_pow_fast(r, s_sig, p)) % p
        print("yA = g^a mod p = {}".format(yA))
        print("g^M mod p = {}".format(left))
        print("y^r * r^s mod p = {}".format(right))
        if left == right:
            print("Conclusion : signature VALIDE")
        else:
            print("Conclusion : signature INVALIDE")
        print("Étapes puissance : Menu (7).")

def eds_crypto_menu():
    sep("EDS / DS - Crypto (léger)")
    print("1) RSA (générique)")
    print("2) ElGamal (générique)")
    print("3) Retour")
    ch = input("> Choix : ").strip()
    if ch == "1":
        eds_rsa_menu()
    elif ch == "2":
        eds_elgamal_menu()

def menu():
    sep("MENU")
    print("1) Décomp. facteurs premiers")
    print("2) PGCD / Bézout")
    print("3) Inverse mod m")
    print("4) Équations modulaires")
    print("5) Tables (Z / Z_n)")
    print("6) CRT (théorème des restes chinois)")
    print("7) Puissance mod m")
    print("8) EDS/DS Crypto (léger)")
    print("9) Quitter")
    choice = input("> Choix : ").strip()

    if choice == "1":
        show_factorization_and_option_gcd()
    elif choice == "2":
        run_pgcd_bezout()
    elif choice == "3":
        run_inverse()
    elif choice == "4":
        equations_menu_option()
    elif choice == "5":
        run_tables()
    elif choice == "6":
        solve_system_crt_coprime()
    elif choice == "7":
        run_pow_mod()
    elif choice == "8":
        eds_crypto_menu()
    elif choice == "9":
        print("Quitter le programme.")
        return
    else:
        print("Choix inconnu.")

menu()