Modular Linear Equation
Résoudre l'équation linéaire modulaire ax≡b (mod n) : des solutions existent si et seulement si gcd(a,n) divise b, et il y en a exactement gcd(a,n).
Objectif
Résoudre des équations modulaires et comprendre quand la division est possible en arithmétique modulaire.
Mécanisme
Soit d=gcd(a,n). Si d ne divise pas b, il n'y a pas de solution. Sinon, on utilise l'algorithme d'Euclide étendu pour trouver l'unique solution de (a/d)·x0 ≡ b/d (mod n/d) ; toutes les solutions sont x0 + k*(n/d) mod n pour k=0..d-1.
Cas d’usage
- Résolution d'équations cryptographiques
- Arithmétique modulaire
- Calcul en théorie des nombres