Addition, soustraction, multiplication, exponentiation et inverse modulaires. Apprenez les opérations modulaires utilisées dans le chiffrement RSA.
L'opération modulo (a mod m) est le reste de la division de a par m. Exemple : 17 mod 5 = 2. Utilisée quotidiennement dans les calculs d'horloge (format 24 heures) et les calculs de jours de la semaine. Essentielle en programmation pour la rotation des index de tableaux et les fonctions de hachage.
Addition modulaire : (a + b) mod m. Multiplication modulaire : (a × b) mod m. Pour éviter les dépassements de capacité lors du calcul de grands nombres, on applique le modulo à chaque étape. Exemple : (12 + 8) mod 5 = 20 mod 5 = 0.
Lors du calcul de a^b mod m, l'exponentiation directe rend les nombres trop grands. L'algorithme d'exponentiation rapide par diviser-pour-régner permet un calcul en temps O(log b). C'est l'opération centrale du chiffrement RSA.
L'inverse modulaire est le x tel que (a × x) mod m = 1. Il n'existe que si a et m sont premiers entre eux. Il se calcule en temps O(log m) grâce à l'algorithme d'Euclide étendu. Utilisé pour le déchiffrement et le calcul de fractions.
RSA est un système de cryptographie à clé publique reposant sur l'exponentiation modulaire et l'inverse modulaire. Chiffrement : c = m^e mod n, Déchiffrement : m = c^d mod n. Il exploite la difficulté de factoriser n, le produit de deux grands nombres premiers.