Modular Arithmetic
Modulare Arithmetik nimmt Reste nach Ganzzahloperationen und hält Ergebnisse in [0, n); sie ist die Grundlage der Zahlentheorie und Kryptographie.
Zweck
Operationen in einem endlichen Bereich geschlossen halten, die Basis von RSA, Diffie-Hellman und weiteren Kryptoverfahren.
Mechanismus
(a + b) mod n und (a × b) mod n sind modulo n definiert. Das modulare Inverse a^(-1) erfüllt a·a^(-1) ≡ 1 (mod n); es existiert, wenn gcd(a,n)=1, und wird mit dem erweiterten euklidischen Algorithmus gefunden. Nach dem kleinen Satz von Fermat gilt a^(p-1) ≡ 1 (mod p) für Primzahl p.
Anwendungsfälle
- RSA-Verschlüsselung und -Entschlüsselung
- Diffie-Hellman-Schlüsselaustausch
- Sharding per Hash-Modulo
- Prüfsummenberechnung
Beispiele
- Eingabe
(7 + 8) mod 5Output015 mod 5 = 0
Häufige Fehler
- Negative modulo behaves differently across languages
- Know your language's behavior or normalize with ((a%n)+n)%n
Verwandte Begriffe
BigInteger
BigInteger ist ein Ganzzahltyp mit beliebiger Genauigkeit, der nicht an eine feste Wortbreite gebunden ist, und dient Berechnungen jenseits des nativen Integerbereichs (etwa Kryptographie und Kombinatorik). GLOSSAR
Prime Number
Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und sich selbst teilbar ist; sie ist der Baustein der Zahlentheorie, und jede ganze Zahl zerfällt eindeutig in Primfaktoren. GLOSSAR
GCD
Der ggT (größter gemeinsamer Teiler) ist die größte positive ganze Zahl, die zwei oder mehr ganze Zahlen teilt, effizient berechnet mit dem euklidischen Algorithmus. GLOSSAR