Modulo-Rechner

Modulare Addition, Subtraktion, Multiplikation, Exponentiation und Inverse. Lernen Sie die modularen Operationen kennen, die bei der RSA-Verschlüsselung verwendet werden.

Grundlegendes Modulo — Modulare Addition — Modulare Subtraktion — Modulare Multiplikation — Modulare Exponentiation — Modulare Inverse —

RATGEBER

Mehr erfahren

Grundlagen der Modulo-Operation

Die Modulo-Operation (a mod m) ist der Rest der Division von a durch m. Beispiel: 17 mod 5 = 2. Wird täglich bei Uhrzeitberechnungen (24-Stunden-System) und bei der Berechnung des Wochentags verwendet. In der Programmierung essenziell für das zyklische Umlaufen von Array-Indizes und für Hashfunktionen.

Modulare Addition und Multiplikation

Modulare Addition: (a + b) mod m. Modulare Multiplikation: (a × b) mod m. Um bei der Berechnung großer Zahlen einen Überlauf zu vermeiden, wird bei jedem Schritt der Modulo genommen. Beispiel: (12 + 8) mod 5 = 20 mod 5 = 0.

Modulare Exponentiation - Schnelle Berechnung

Bei der Berechnung von a^b mod m werden die Zahlen bei direkter Potenzierung zu groß. Der Schnellpotenzierungs-Algorithmus nach dem Prinzip „Teile und herrsche“ ermöglicht eine Berechnung in O(log b) Zeit. Dies ist die zentrale Operation der RSA-Verschlüsselung.

Modulare Inverse - Erweiterter Euklidischer Algorithmus

Die modulare Inverse ist x, sodass (a × x) mod m = 1 gilt. Sie existiert nur, wenn a und m teilerfremd sind. Sie wird mit dem erweiterten euklidischen Algorithmus in O(log m) Zeit berechnet. Wird bei der Entschlüsselung und bei Bruchrechnungen verwendet.

RSA-Verschlüsselung und modulare Operationen

RSA ist ein Public-Key-Kryptosystem, das auf modularer Exponentiation und Inverse basiert. Verschlüsselung: c = m^e mod n, Entschlüsselung: m = c^d mod n. Es beruht auf der Schwierigkeit, n, das Produkt zweier großer Primzahlen, zu faktorisieren.

Häufig gestellte Fragen

Was ist der Unterschied zwischen Modulo und Division?

Die Division a ÷ m liefert einen Quotienten (wie oft m in a passt), während die Modulo-Operation a mod m nur den Rest dieser Division zurückgibt. Bei 17 ÷ 5 ist der Quotient 3 und der Rest (17 mod 5) ist 2.

Wie verhält sich Modulo bei negativen Zahlen?

Das hängt von der Konvention ab. In der Mathematik wird das Ergebnis meist so definiert, dass es immer positiv oder null ist (z. B. -7 mod 3 = 2), während manche Programmiersprachen das Vorzeichen des Dividenden übernehmen. Dieser Rechner verwendet die mathematische Konvention mit nicht-negativem Ergebnis.

Wann existiert keine modulare Inverse?

Eine modulare Inverse von a modulo m existiert nur, wenn a und m teilerfremd sind, also ihr größter gemeinsamer Teiler 1 ist. Ist zum Beispiel a=4 und m=8 (ggT=4), gibt es keine Inverse, da die Zahlen nicht teilerfremd sind.

Warum wird für a^b mod m nicht einfach zuerst a^b berechnet?

Bei großen Exponenten würde a^b eine astronomisch große Zahl ergeben, die den Speicher sprengt und die Berechnung extrem verlangsamt. Der Schnellpotenzierungs-Algorithmus nimmt bei jedem Zwischenschritt den Modulo, sodass die Zahlen klein bleiben und die Berechnung in O(log b) Zeit abläuft.

Wofür wird Modulo außerhalb der Kryptographie im Alltag genutzt?

Modulo wird zum Beispiel bei der Uhrzeitberechnung genutzt (23 Uhr + 3 Stunden = 2 Uhr, also (23+3) mod 24), bei der Bestimmung des Wochentags, beim zyklischen Durchlaufen von Array-Indizes in der Programmierung und bei Prüfsummen wie der ISBN- oder IBAN-Validierung.