Modular Linear Equation
Lösen der modularen linearen Gleichung ax≡b (mod n): Lösungen existieren genau dann, wenn gcd(a,n) b teilt, und es gibt genau gcd(a,n) davon.
Zweck
Modulare Gleichungen lösen und verstehen, wann eine Division in modularer Arithmetik möglich ist.
Mechanismus
Sei d=gcd(a,n). Teilt d nicht b, gibt es keine Lösung. Andernfalls findet der erweiterte euklidische Algorithmus die eindeutige Lösung von (a/d)·x0 ≡ b/d (mod n/d); alle Lösungen sind x0 + k*(n/d) mod n für k=0..d-1.
Anwendungsfälle
- Kryptographische Gleichungslösung
- Modulare Arithmetik
- Zahlentheoretische Berechnungen