Arithmétique modulaire

#Arithmétique modulaireCopier le lien

L'arithmétique modulaire est un système de calcul où les nombres "bouclent" après avoir atteint une certaine valeur, appelée le module. Elle est fondamentale en cryptographie, en théorie des nombres et en informatique.

#CongruencesCopier le lien

Deux entiers a et b sont congrus modulo n si leur différence est un multiple de n :

1a ≡ b (mod n)  ⟺  n divise (a - b)

#PropriétésCopier le lien

• Réflexivité : a ≡ a (mod n)
• Symétrie : a ≡ b (mod n) ⟹ b ≡ a (mod n)
• Transitivité : a ≡ b (mod n) et b ≡ c (mod n) ⟹ a ≡ c (mod n)

#OpérationsCopier le lien

• Addition : (a + b) mod n = ((a mod n) + (b mod n)) mod n
• Multiplication : (a × b) mod n = ((a mod n) × (b mod n)) mod n
• Soustraction : (a - b) mod n = ((a mod n) - (b mod n)) mod n

#PGCD (Plus Grand Commun Diviseur)Copier le lien

Le PGCD de deux entiers est le plus grand entier qui les divise tous les deux.

#Algorithme d'EuclideCopier le lien

1def pgcd(a, b):2    while b:3        a, b = b, a % b4    return a

#PropriétésCopier le lien

• Commutatif : pgcd(a, b) = pgcd(b, a)
• Associatif : pgcd(a, pgcd(b, c)) = pgcd(pgcd(a, b), c)
• Identité : pgcd(a, 0) = |a|

#Inverse modulaireCopier le lien

L'inverse modulaire de a modulo m est un entier x tel que :

1(a × x) ≡ 1 (mod m)

Un inverse modulaire existe si et seulement si pgcd(a, m) = 1 (a et m sont copremiers).

#Algorithme d'Euclide étenduCopier le lien

1def euclide_etendu(a, b):2    if b == 0:3        return a, 1, 04    else:5        d, x, y = euclide_etendu(b, a % b)6        return d, y, x - (a // b) * y7 8def inverse_modulaire(a, m):9    d, x, y = euclide_etendu(a, m)10    if d != 1:11        return None  # Pas d'inverse12    else:13        return x % m

#Exercice : Implémentation d'opérations modulaires et chiffrement de CésarCopier le lien

Implémentez une bibliothèque d'arithmétique modulaire et utilisez-la pour créer un chiffrement de César.

#InstructionsCopier le lien

1. Implémentez les fonctions de base :
   • mod(a, n) : Calcul du modulo (toujours positif)
   • pgcd(a, b) : Calcul du PGCD
   • inverse_modulaire(a, m) : Calcul de l'inverse modulaire
2. Implémentez le chiffrement de César :
   • chiffrer_cesar(message, decalage) : Chiffre un message
   • dechiffrer_cesar(message_chiffre, decalage) : Déchiffre un message
3. Ajoutez une fonction pour casser le chiffre de César par force brute.

#Exemple de codeCopier le lien

1def mod(a, n):2    """Calcul du modulo toujours positif"""3    return a % n4 5def pgcd(a, b):6    """Calcul du PGCD par l'algorithme d'Euclide"""7    while b:8        a, b = b, a % b9    return abs(a)10 11def euclide_etendu(a, b):12    """Algorithme d'Euclide étendu"""13    if b == 0:14        return a, 1, 0

#ApplicationsCopier le lien

#HachageCopier le lien

• Tables de hachage : Utilisation de modulo pour distribuer les clés
• Fonctions de hachage : Calculs modulaires pour garantir des valeurs dans une plage

#CryptographieCopier le lien

• Chiffre de César : Chiffrement par décalage modulaire
• RSA : Opérations modulaires avec de grands nombres premiers
• Courbes elliptiques : Arithmétique sur des points modulo p

#Théorie des nombresCopier le lien

• Petit théorème de Fermat : a^(p-1) ≡ 1 (mod p) si p premier
• Théorème des restes chinois : Résolution de systèmes de congruences
• Tests de primalité : Algorithmes probabilistes basés sur des propriétés modulaires