Sieben hoch 256 hat 217 Stellen, und man schreibt keine davon
Veröffentlicht am 27.10.2026 · 3 Min. Lesezeit · Alltags-Rechner
Daniel Okonkwo — Front-end-Entwickler und Tech-Redakteur bei OneKitly
Web-Performance · Dateiformate
Anhand von 2 Quellen geprüft
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.
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.
| Ausdruck | Stellen ausgeschrieben | Ergebnis |
|---|---|---|
| 7²⁵⁶ mod 13 | 217 | 9 |
| 2¹⁰⁰⁰ mod 1.000.000.007 | 302 | 688.423.210 |
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?