Rechner für modulare Potenzen

Die modulare Potenzierung berechnet den Rest, wenn eine ganzzahlige Basis mit einem nichtnegativen ganzzahligen Exponenten potenziert und durch einen positiven Modul geteilt wird. Der Ausdruck a^b mod m fragt nach dem eindeutigen Rest von 0 bis m - 1, der zu a^b kongruent ist. Eine direkte Berechnung wird schnell unpraktikabel, weil Potenzen enorme Größen erreichen, selbst wenn der abschließende Rest klein ist. Dieser Rechner vermeidet es, diese riesige ganze Zahl als Zwischenergebnis zu erzeugen. Das effiziente Verfahren heißt binäre Exponentiation, wiederholtes Quadrieren oder Quadrieren und Multiplizieren. Der Exponent wird binär dargestellt und bitweise verarbeitet. Zunächst wird die Basis modulo m reduziert. In jedem Schritt wird der aktuelle Faktor quadriert und modulo m reduziert. Ist das zugehörige Exponentenbit eins, wird dieser Faktor mit dem Ergebnis multipliziert und sofort wieder modulo m reduziert. Durch die laufende Reduktion bleiben die Zwischenwerte kleiner als das Quadrat des Moduls. Die Anzahl der Schritte ist nur proportional zum Logarithmus des Exponenten. Eine Potenz mit dem Exponenten eine Milliarde benötigt deshalb nur etwa dreißig Quadrierungsstufen statt einer Milliarde wiederholter Multiplikationen. Die angezeigte Anzahl unterscheidet Quadrierungen von den ausgewählten Multiplikationen für die Eins-Bits des Exponenten. Bei Exponent null wird korrekt 1 mod m zurückgegeben. In der modularen Arithmetik gelten Zahlen mit gleichem Rest als gleichwertig. Beispielsweise sind 17 und 5 modulo 12 kongruent, weil beide den Rest 5 liefern. Auch eine negative Basis wird unterstützt und zunächst auf einen nichtnegativen Rest normalisiert. Der Exponent muss in diesem Rechner nichtnegativ sein. Negative modulare Exponenten erfordern ein multiplikatives Inverses modulo m, das nur existiert, wenn Basis und Modul teilerfremd sind. Modulare Potenzen sind grundlegend für Zahlentheorie und moderne Kryptografie. RSA-Verschlüsselung und -Signaturen potenzieren Nachrichten mit großen Exponenten modulo einer zusammengesetzten Zahl. Der Diffie-Hellman-Schlüsselaustausch und viele Verfahren mit diskreten Logarithmen nutzen Potenzen modulo einer Primzahl. Dieselbe Operation kommt auch bei Primzahltests, Pseudozufallszahlengeneratoren, Prüfsummen, zyklischen Mustern und Programmierwettbewerben zum Einsatz. Alle drei Felder werden als exakte Ganzzahlen beliebiger Größe statt als Gleitkommazahlen verarbeitet. Dadurch bleiben auch jenseits der üblichen sicheren Ganzzahlgrenze von JavaScript sämtliche Ziffern erhalten. Der Modul muss größer als eins sein; Kommas oder Dezimalpunkte dürfen nicht eingegeben werden. Zur manuellen Kontrolle reduzieren Sie zuerst die Basis und prüfen kleine Exponenten durch wiederholtes Multiplizieren, wobei Sie nach jedem Schritt den Rest bilden.