euclide_et_inverse.py

Note de lecture générée automatiquement

Le vrai fichier est scripts/maths/euclide_et_inverse.py (Obsidian n’affiche pas les scripts eux-mêmes). Ne modifie pas cette note : modifie le script, puis relance python3 generer_vues_obsidian.py dans le dossier scripts.

• À quoi il sert : PGCD, facteurs, modulo, inverse
• Lancer (dans le dossier scripts/maths/) : python3 euclide_et_inverse.py pgcd 592 104
• Fiche : M01 - Arithmétique et chiffrement affine
• Retour : 00 - Tous les scripts

Code

#!/usr/bin/env python3
"""
euclide_et_inverse.py — PGCD avec les étapes d'Euclide, décomposition en
facteurs premiers, congruence et inverse modulaire (pour le chiffrement affine).
 
Utilisation :
    python3 euclide_et_inverse.py pgcd 592 104
    python3 euclide_et_inverse.py facteurs 168
    python3 euclide_et_inverse.py modulo -178 26
    python3 euclide_et_inverse.py inverse 7 26
    python3 euclide_et_inverse.py table 26        # tous les inverses modulo 26
"""
import sys
 
 
def pgcd_avec_etapes(a: int, b: int) -> int:
    print(f"Algorithme d'Euclide pour pgcd({a}, {b}) :")
    while b != 0:
        quotient, reste = divmod(a, b)
        print(f"  {a} = {b} × {quotient} + {reste}")
        a, b = b, reste
    print(f"=> dernier reste non nul : pgcd = {a}")
    return a
 
 
def facteurs_premiers(n: int) -> dict:
    facteurs = {}
    diviseur = 2
    while diviseur * diviseur <= n:
        while n % diviseur == 0:
            facteurs[diviseur] = facteurs.get(diviseur, 0) + 1
            n //= diviseur
        diviseur += 1
    if n > 1:
        facteurs[n] = facteurs.get(n, 0) + 1
    return facteurs
 
 
def ecrire_facteurs(facteurs: dict) -> str:
    return " × ".join(f"{p}^{e}" if e > 1 else str(p) for p, e in sorted(facteurs.items()))
 
 
def inverse_modulaire(a: int, n: int) -> int:
    # Euclide étendu : trouve u tel que a*u ≡ 1 (mod n)
    ancien_r, r = a % n, n
    ancien_u, u = 1, 0
    while r != 0:
        quotient = ancien_r // r
        ancien_r, r = r, ancien_r - quotient * r
        ancien_u, u = u, ancien_u - quotient * u
    if ancien_r != 1:
        raise ValueError(f"{a} n'a pas d'inverse modulo {n} (pgcd = {ancien_r})")
    return ancien_u % n
 
 
if __name__ == "__main__":
    if len(sys.argv) < 3:
        sys.exit(__doc__)
    commande = sys.argv[1]
    if commande == "pgcd":
        pgcd_avec_etapes(int(sys.argv[2]), int(sys.argv[3]))
    elif commande == "facteurs":
        nombre = int(sys.argv[2])
        decomposition = facteurs_premiers(nombre)
        diviseurs = [d for d in range(1, nombre + 1) if nombre % d == 0]
        print(f"{nombre} = {ecrire_facteurs(decomposition)}")
        print(f"Diviseurs ({len(diviseurs)}) : {diviseurs}")
    elif commande == "modulo":
        a, n = int(sys.argv[2]), int(sys.argv[3])
        quotient, reste = divmod(a, n)          # Python arrondit vers -infini : reste toujours >= 0
        print(f"{a} = {n} × ({quotient}) + {reste}   donc   {a} ≡ {reste} [{n}]")
    elif commande == "inverse":
        a, n = int(sys.argv[2]), int(sys.argv[3])
        inverse = inverse_modulaire(a, n)
        print(f"Inverse de {a} modulo {n} : {inverse}   (vérif : {a} × {inverse} = {a * inverse} ≡ 1 [{n}])")
    elif commande == "table":
        n = int(sys.argv[2])
        for a in range(1, n):
            try:
                print(f"  {a:>3} -> {inverse_modulaire(a, n):>3}")
            except ValueError:
                pass
    else:
        sys.exit(__doc__)