1. Équation de congruence linéaire ax ≡ b (mod m) :
- Existence de solutions :L'équation a une solution si et seulement si pgcd(a, m) divise b (c'est-à-dire que b est divisible par pgcd(a, m))
- Nombre de solutions :Si des solutions existent, il y a d = pgcd(a, m) solutions distinctes modulo m
- Méthode de résolution :
- Calculer d = pgcd(a, m)
- Vérifier si d divise b ; sinon, il n'y a pas de solution
- Diviser les deux côtés de l'équation par d : (a/d)x ≡ (b/d) (mod m/d)
- Utiliser l'algorithme d'Euclide étendu pour trouver l'inverse de a/d modulo m/d
- Calculer x₀ = a' × (b/d) mod (m/d)
- Solution générale : x = x₀ + k(m/d), où k = 0, 1, ..., d-1
2. Équation de congruence exponentielle a^x ≡ b (mod m) (Problème du logarithme discret) :
- Description du problème :Étant donnés a, b, m, trouver le plus petit entier non négatif x tel que a^x ≡ b (mod m)
- Existence de solutions :
- Si pgcd(a, m) = 1 et que b est un élément du groupe cyclique généré par a modulo m, alors une solution existe
- Méthode de vérification : énumérer les puissances de a jusqu'à ce que b soit trouvé ou qu'un cycle complet soit achevé
- Méthode de résolution :
- Recherche par force brute dans un petit intervalle :Énumérer x = 0, 1, 2, ... jusqu'à ce qu'une solution soit trouvée ou que la limite de recherche soit atteinte
- Algorithme Baby-step Giant-step :Complexité temporelle O(√m), adapté aux problèmes de taille moyenne
- Algorithme de Pollard (rho) :Applicable pour les grands modules premiers
- Périodicité :Si x₀ est une solution, alors x = x₀ + kφ(m) est aussi une solution (où φ(m) est l'indicatrice d'Euler)
3. Scénarios d'application :
- Cryptographie :RSA, échange de clés Diffie-Hellman, chiffrement ElGamal
- Recherche en théorie des nombres :Racines primitives, résidus quadratiques, théorème des restes chinois
- Génération de nombres aléatoires :Générateur congruentiel linéaire (LCG)
- Fonctions de hachage :Application de l'arithmétique modulaire dans les tables de hachage
- Programmation compétitive :Exponentiation rapide, inverse modulaire, problèmes de théorie des nombres
Complexité algorithmique :
- Équations de congruence linéaires :O(log m) (Complexité de l'algorithme d'Euclide étendu)
- Équations de congruence exponentielles (force brute) :O(n), où n est la limite de recherche
- Équations de congruence exponentielles (BSGS) :O(√m), nécessite un espace supplémentaire
Théorèmes importants :
- Théorème de Bézout :L'équation ax + my = pgcd(a, m) a toujours des solutions entières
- Petit théorème de Fermat :Si p est premier et pgcd(a, p) = 1, alors a^(p-1) ≡ 1 (mod p)
- Théorème d'Euler :Si pgcd(a, m) = 1, alors a^φ(m) ≡ 1 (mod m)
- Théorème des restes chinois :Peut résoudre des systèmes de congruences