Zum Inhalt springen
OneKitly

Sieben hoch 256 hat 217 Stellen, und man schreibt keine davon

Veröffentlicht am 27.10.2026 · 3 Min. Lesezeit · Alltags-Rechner

Daniel Okonkwo

Daniel Okonkwo — Front-end-Entwickler und Tech-Redakteur bei OneKitly

Web-Performance · Dateiformate

Anhand von 2 Quellen geprüft

Profil ansehen →
Kurz gesagt

Sieben hoch 256 ist eine Zahl mit 217 Stellen, und ihren Rest bei Division durch dreizehn zu finden verlangt keine einzige davon. Der Kniff: Der Rest darf bei jedem Schritt genommen werden. Quadriere sieben zu 49, reduziere auf 10, quadriere zu 100, reduziere auf 9 und mach weiter — insgesamt acht Quadrierungen, denn 256 ist zwei hoch acht, und die Antwort lautet 9. Dieselbe Methode bewältigt 2¹⁰⁰⁰ modulo 1.000.000.007 und liefert 688.423.210, während der ehrliche Wert 302 Stellen hat. Keine Zwischenzahl übersteigt je das Quadrat des Moduls, und genau das macht die Rechnung auf einer Maschine mit fester Zahlbreite möglich.

Werbung

7²⁵⁶ mod 13 ist 9, und 2¹⁰⁰⁰ mod 1.000.000.007 ist 688.423.210. Beides ergibt sich aus acht bzw. zehn Quadrierungen, wobei keine Zahl der Rechnung das Quadrat des Moduls übersteigt.

Acht Multiplikationen statt zweihundertfünfundfünfzig

Eine Potenz durch wiederholtes Multiplizieren zu berechnen kostet einen Schritt je Exponenteneinheit. Quadrieren verdoppelt den Exponenten jedes Mal; 256 zu erreichen braucht also acht statt 255 Schritte, und einen Exponenten mit dreihundert Stellen rund tausend. Einen Exponenten, der keine Zweierpotenz ist, behandelt man, indem man ihn binär schreibt, bei jedem Bit quadriert und dort mit der Basis multipliziert, wo das Bit gesetzt ist — deshalb beschreibt man das Verfahren oft als Lesen der Binärziffern des Exponenten von einem Ende zum anderen. Der Aufwand ist proportional zur Bitzahl des Exponenten, nicht zum Exponenten selbst.

Warum dieselben acht Schritte konstant lange dauern

Jeder Zwischenwert wird sofort reduziert, bleibt also unter dem Modul, und sein Quadrat passt in die doppelte Modulbreite. Diese Schranke erklärt, warum der Aufwand je Schritt nicht mit dem Exponenten wächst und warum eine Implementierung ihre Arithmetik einmal dimensionieren und die Frage danach vergessen kann. Sie erklärt auch das klägliche Scheitern der naiven Alternative: erst die 217-stellige Zahl zu berechnen und am Ende zu reduzieren ist mathematisch korrekt und verlangt Langzahlarithmetik, mehrere hundert Byte je Wert und weit mehr Zeit als die gesamte modulare Rechnung.

Was die Abkürzung vermeidet
AusdruckStellen ausgeschriebenErgebnis
7²⁵⁶ mod 132179
2¹⁰⁰⁰ mod 1.000.000.007302688.423.210
Modulare-Exponentiation-RechnerBerechne aᵇ mod n effizient mit schneller Exponentiation (Quadrieren und Multiplizieren) und Großzahlen — selbst riesige Potenzen reduzieren sich im Sekundenbruchteil. Eine negative oder zu große Basis wird zuerst in den Bereich 0…n−1 gebracht, und negative Exponenten werden unterstützt, wenn die Basis modulo n invertierbar ist. Dies ist die Kernoperation von RSA, Diffie–Hellman und Primzahltests.Tool ausprobieren →
Werbung

Häufige Fragen

Warum wird 1.000.000.007 so oft als Modul genutzt?
Weil sie prim ist, knapp unter einer Milliarde liegt und ihr Quadrat in eine 64-Bit-Ganzzahl passt. Prim zu sein heißt, dass jeder von null verschiedene Wert ein multiplikatives Inverses hat: Die Division funktioniert, nichts entartet. Knapp unter einer Milliarde hält die Ergebnisse lesbar und macht Kollisionen bei hashartiger Verwendung selten. Dass ihr Quadrat in ein Maschinenwort passt, erlaubt das Multiplizieren zweier reduzierter Werte ohne Überlauf und ohne Langzahlarithmetik. Diese drei Eigenschaften zusammen erklären allein die Häufigkeit dieser Zahl in Aufgaben des Wettbewerbsprogrammierens.
Verrät die Rechenzeit etwas?
Sie kann es, und das ist eine reale Angriffsklasse, keine theoretische Sorge. Die naive Fassung multipliziert nur dort, wo ein Bit des Exponenten gesetzt ist; die Laufzeit hängt also davon ab, wie viele Bits gesetzt sind — und ist der Exponent ein privater Schlüssel, verlässt damit Information die Maschine über die Uhr. Ernsthafte Implementierungen führen die Multiplikation daher bedingungslos aus und verwerfen das Ergebnis bei nicht gesetztem Bit, zahlen also konstante Kosten, damit die Zeit vom Geheimnis unabhängig ist. Dieselbe Disziplin taucht überall auf, wo eine Verzweigung von privaten Daten abhängt.

Artikel, die dich interessieren könnten

Alle Ratgeber →

Ähnliche Tools

Quellen

Hast du einen Fehler in diesem Artikel entdeckt?