Modulo-Rechnung — Reste verstehen
Definition · Modulo
a mod n = Rest bei Division a / n.
Rechenregeln
(a + b) mod n = ((a mod n) + (b mod n)) mod n
(a · b) mod n = ((a mod n) · (b mod n)) mod n
(a^k) mod n = wiederholte Anwendung — nicht auspotenzieren!Schnelles PotenzierenBei a^k mod n nicht erst a^k ausrechnen (zu groß!) — sondern Square-and-Multiply: a² mod n, dann (a²)² mod n, usw. Logarithmisch viele Schritte.
Anwendung — Wochentag in 100 Tagen
Heute: Mittwoch (= 3, wenn So = 0)
In 100 Tagen: (3 + 100) mod 7 = 103 mod 7 = 5 → Freitag.Multiplikatives Inverses mod n
a⁻¹ mod n existiert genau dann, wenn ggT(a, n) = 1. Berechnung: erweiterter Euklid-Algorithmus.
Beispiel: Inverses von 3 mod 7?
ggT(3, 7) = 1 → existiert.
3 · 5 = 15 ≡ 1 mod 7 → Inverses: 5.