Die modulare Potenzierung – die Berechnung von a^b mod m – sieht aus wie eine einfache Rechenübung, aber ihre effiziente Berechnung macht die moderne Public-Key-Kryptographie praktisch. Dieser Rechner berechnet a^b mod m mithilfe des Quadrat-und-Multiplikations-Algorithmus und zeigt Stück für Stück genau, wie es funktioniert.
Warum nicht einfach a^b berechnen und dann den Rest bilden?
Bei kleinen Zahlen funktioniert die direkte Berechnung von a^b und die anschließende Reduzierung von mod m einwandfrei. Aber kryptografische Operationen verwenden Exponenten und Module mit einer Länge von Hunderten von Ziffern – a^b selbst hätte weit mehr Ziffern als Atome im beobachtbaren Universum, lange bevor Sie jemals zum Schritt „mod m“ gelangen. Square-and-Multiply vermeidet dies vollständig, indem Modulo m nach jeder Quadrierung und Multiplikation reduziert wird, sodass kein Zwischenwert jemals m überschreitet. In Kombination mit der Tatsache, dass statt b − 1 nur etwa log2(b)-Multiplikationen erforderlich sind, ist dies der Grund dafür, dass Operationen wie die RSA-Verschlüsselung mit einem 2048-Bit-Exponenten in Millisekunden abgeschlossen sind und nicht rechnerisch unmöglich sind.
Lesen der Registerkarten „Quadrier- und Multiplikationsschritte“ und „Binärer Exponent“.
Der Algorithmus durchsucht die Binärziffern des Exponenten von der höchstwertigen zur niedrigstwertigen Ziffer. Bei jedem Bit quadriert es das laufende Ergebnis und reduziert mod m; Wenn dieses Bit eine 1 ist, wird es ebenfalls mit der Basis multipliziert und erneut reduziert. Auf der Registerkarte „Binärer Exponent“ wird angezeigt, welche Bits 1 und welche 0 sind – jedes 1-Bit ist eine zusätzliche Multiplikation über die Quadrierungen hinaus, die jedes Bit erfordert. Ein 20-Bit-Exponent, egal wie groß die Dezimalzahl ist, die er darstellt, kostet immer noch nur 20 Quadrierungen und höchstens 20 Multiplikationen.
Grenzen und Randfälle
Dieser Rechner unterstützt nur nicht negative Exponenten. Ein negativer Exponent – wie a^(-1) mod m – erfordert die Berechnung der modularen Umkehrung von a, die nur existiert, wenn a und m teilerfremd sind und einen völlig anderen Algorithmus (den erweiterten euklidischen Algorithmus) erfordert; es wird hier nicht unterstützt. Ein Modul von 1 ergibt immer 0, da jede ganze Zahl durch 1 teilbar ist. Und obwohl die Basis als negativ eingegeben werden kann, wird sie vor der Ausführung des Algorithmus auf den Bereich [0, m) normalisiert, was der mathematischen Standardkonvention entspricht, dass ein mod m immer nicht negativ ist.