Modulare-Arithmetik-Rechner
Berechnen Sie a mod n, modulare Addition, Multiplikation und Potenz (aᵇ mod n) — Uhrzeigerarithmetik im Handumdrehen.
1.225 Aufrufe
Wie modulare Arithmetik funktioniert
a mod n stellt eine einfache Frage: Welcher Rest bleibt, wenn a durch n geteilt wird? Formal gilt a mod n = a − n × floor(a ÷ n), und nach mathematischer Konvention liegt das Ergebnis immer zwischen 0 und n−1. Am anschaulichsten lässt sich das an einem Zifferblatt vorstellen: Stunden zählen nicht endlos weiter, sondern wickeln sich bei 12 (oder 24) um. Angenommen es ist 15:00 Uhr und Sie möchten wissen, wie spät es 10 Stunden später ist — Sie erhalten nicht "25:00", sondern berechnen (15 + 10) mod 24 = 1, also 01:00 Uhr am nächsten Tag. Jeder Wert durchläuft denselben Satz an "Plätzen" erneut, und genau dieses Umwickeln ist es, was n in a mod n bewirkt.
Dieser Rechner erweitert dieselbe Idee auf drei verwandte Operationen: modulare Addition (a + b) mod n, modulare Multiplikation (a × b) mod n und modulare Potenzierung aᵇ mod n. Letztere wirkt harmlos, ist aber die wichtigste Operation der modernen Kryptografie überhaupt. Würde man sie naiv berechnen — erst a hoch b bilden und danach den Rest bestimmen —, entstünden bei realen Schlüsselgrößen Zahlen mit Millionen von Stellen, noch bevor der Modulo-Schritt überhaupt greift. Stattdessen verwendet das Tool den Square-and-Multiply-Algorithmus: Die Basis wird bei jedem Schritt quadriert und sofort modulo n reduziert, sodass die Zwischenwerte nie über die Größe von n hinauswachsen, egal wie groß b ist. Genau das macht exakte Ergebnisse selbst bei hunderte Stellen langen Exponenten möglich.
Was Sie wissen sollten
- Kryptografie: RSA und der Diffie-Hellman-Schlüsselaustausch beruhen beide auf modularer Potenzierung mit sehr großen Primzahlen — eine Nachricht zu verschlüsseln bedeutet im Kern, aᵇ mod n zu berechnen, wobei a, b und n jeweils hunderte Stellen lang sind.
- Hash-Funktionen: die meisten Hash-Verfahren reduzieren eine Eingabe beliebiger Größe mittels Modulo-Operation auf einen festen "Bucket" — deshalb taucht mod überall in Hash-Tabellen, Prüfsummen und Lastverteilungslogik auf.
- Kalender und Uhren: Wochentagsberechnungen, 12/24-Stunden-Umrechnungen und Kalenderzyklen sind allesamt getarnte modulare Arithmetik — daher stammt auch der Spitzname "Uhrzeigerarithmetik".
- Vorzeichenkonventionen unterscheiden sich: Die Mathematik definiert a mod n stets als nicht-negativ, aber viele Programmiersprachen (C, JavaScript, Java) geben stattdessen einen Rest mit demselben Vorzeichen wie a zurück, was bei der direkten Übertragung von Formeln in Code zu Fehlern führen kann.
Häufig gestellte Fragen
Was ist −7 mod 3?
Dieses Tool folgt der mathematischen Konvention, wonach das Ergebnis immer nicht-negativ ist: −7 mod 3 = 2 (da −7 = −3×3 + 2). Manche Programmiersprachen geben stattdessen −1 zurück, weil sie den Rest mit demselben Vorzeichen wie der Dividend definieren, anstatt ihn immer positiv zu halten.
Wo wird aᵇ mod n im echten Leben verwendet?
Es ist die Kernoperation von RSA und dem Diffie-Hellman-Schlüsselaustausch: eine Nachricht zu verschlüsseln oder ein gemeinsames Geheimnis auszuhandeln bedeutet im Wesentlichen, eine riesige modulare Potenz zu berechnen, oft mit Zahlen von 2048 Bit Länge oder mehr.
Warum verwendet das Uhr-Beispiel mod 24 und nicht mod 12?
Beide funktionieren — eine 12-Stunden-Uhr wickelt sich bei mod 12 um, eine 24-Stunden-Uhr bei mod 24. Der Modul n ist einfach die Größe des Zyklus, der Sie interessiert; wählen Sie die Uhrkonvention, die zu Ihrer Zeitzählung passt.
Ist a mod n dasselbe wie Ganzzahldivision?
Sie sind zwei Hälften derselben Division. a ÷ n (Ganzzahldivision) liefert den Quotienten — wie oft n vollständig in a passt —, während a mod n den Rest liefert. Zusammen ergibt Quotient × n + Rest immer wieder a.
Warum ist Square-and-Multiply schneller, als aᵇ direkt zu berechnen?
Direkte Potenzierung multipliziert a b−1 mal mit sich selbst, und der Zwischenwert wächst ins Unermessliche, lange bevor er modulo n reduziert werden kann. Square-and-Multiply reduziert dagegen nach jedem Quadrierschritt, sodass die beteiligten Zahlen nie wesentlich über die Größe von n hinauswachsen — das verwandelt eine Operation, die bei kryptografischen Schlüsselgrößen länger als das Alter des Universums dauern würde, in eine, die in Millisekunden fertig ist.
Ähnliche Tools
Problem melden
Modulare-Arithmetik-Rechner
Kommentare
Noch keine Kommentare — schreiben Sie den ersten!