Modulare-Arithmetik-Rechner (Mod-Rechner)
Ein Rechner für modulare Arithmetik mit 4 Modi: Grundlegendes Mod, modulare Addition/Subtraktion/Multiplikation, modulare Potenzierung (schnelle Potenzierung durch wiederholtes Quadrieren) und modulares Inverses (erweiterter euklidischer Algorithmus). Berechnet negative Mod-Werte und riesige Exponenten mit BigInt exakt.
Grundlegende Eigenschaften der modularen Arithmetik
| Eigenschaft | Beschreibung |
|---|---|
| (a + b) mod n = ((a mod n) + (b mod n)) mod n | Ob man das Mod vor oder nach der Addition nimmt, das Ergebnis ist genau dasselbe. |
| (a − b) mod n = ((a mod n) − (b mod n) + n) mod n | Da die Subtraktion ein negatives Ergebnis liefern kann, sorgt das abschließende Addieren von n und erneute Mod-n-Nehmen dafür, dass das Ergebnis im Bereich [0, n) bleibt. |
| (a × b) mod n = ((a mod n) × (b mod n)) mod n | Wie bei der Addition ändert das Nehmen des Mods während der Multiplikation nichts am Endergebnis. Diese Eigenschaft bildet die Grundlage für die schnelle Berechnung von Potenzen (wiederholtes Quadrieren). |
| a und n sind teilerfremd ⇔ es existiert ein Inverses von a modulo n | Nur wenn der erweiterte euklidische Algorithmus gcd(a, n) = 1 liefert, existiert ein x (das Inverse), das a × x ≡ 1 (mod n) erfüllt. |
Tipps
- Das Verhalten von Mod bei negativen Zahlen unterscheidet sich je nach Programmiersprache. Dieses Tool folgt der mathematischen Definition (das Ergebnis liegt stets zwischen 0 und n − 1), sodass -7 mod 3 gleich 2 ist, nicht -1.
- Der Potenzierungsmodus verwendet wiederholtes Quadrieren, sodass er auch bei Exponenten mit Hunderten von Stellen sofort ein Ergebnis liefert. Derselbe Algorithmus wird bei der Ver- und Entschlüsselung von RSA eingesetzt.
- Die Uhrzeit ist ein alltägliches Beispiel für modulare Arithmetik: Rechnet man "15 Uhr" in das 12-Stunden-Format um, ergibt sich 15 mod 12 = 3 Uhr.
- Der Inverse-Modus funktioniert, solange a und n teilerfremd sind (ihr größter gemeinsamer Teiler ist 1), selbst wenn n keine Primzahl ist.
- Im Wettbewerbsprogrammieren wird häufig verlangt, die Antwort modulo einer großen Primzahl wie 1.000.000.007 anzugeben, statt der riesigen Rohzahl. Der Potenzierungsmodus dieses Tools eignet sich auch zum manuellen Nachrechnen solcher Aufgaben.
Häufig gestellte Fragen
Übrigens – die "Uhrzeit-Arithmetik" hinter moderner Kryptografie
Modulare Arithmetik (Kongruenz) wird oft als "Uhrzeit-Arithmetik" (clock arithmetic) bezeichnet. Bei einer 12-Stunden-Uhr wird 13 Uhr als "gleich" mit 1 Uhr behandelt – genau das ist die Kongruenz 13 ≡ 1 (mod 12), eine Idee, die sich nur auf den Rest konzentriert, der bleibt, wenn eine Zahl durch einen Modulus (hier 12) geteilt wird. Der deutsche Mathematiker Carl Friedrich Gauß systematisierte die Kongruenznotation "≡" in seinem 1801 erschienenen Werk Disquisitiones Arithmeticae und machte diese Idee damit zu einem Standardwerkzeug der modernen Mathematik.
Diese scheinbar einfache Operation bildet das Fundament der modernen Internetsicherheit. Bei Public-Key-Kryptosystemen wie RSA ist die "modulare Potenzierung" – das Potenzieren einer riesigen Zahl und anschließende Nehmen des Rests modulo n – die zentrale Operation bei Ver- und Entschlüsselung. Da Exponent und Modulus jeweils Hunderte von Stellen haben können, würde ein naives Berechnen der vollständigen Potenz vor dem Rest-Nehmen den Rechenaufwand explodieren lassen. Wiederholtes Quadrieren dagegen erfordert nur eine Anzahl von Multiplikationen, die proportional zur Ziffernzahl des Exponenten ist, wodurch es praktikabel wird.
Auch die Berechnung modularer Inverser mittels des erweiterten euklidischen Algorithmus ist eine grundlegende Technik, die in der gesamten Informatik zum Einsatz kommt – von der Kryptografie über die Codierungstheorie bis zum Design von Hash-Funktionen. Dass eine "über 2000 Jahre alte Arithmetik" und "modernste Sicherheitstechnologie" auf demselben mathematischen Fundament beruhen, ist ein eindrucksvolles Symbol für die Universalität der Zahlentheorie.