Die Zahl 2^100 ist 1267650600228229401496703205376, einunddreißig Ziffern, und der Bildschirm zeigt sie als 1.2676506002282⋅10+30. Fragen Sie im selben Fenster nach 2^100 mod 7, und die Antwort ist 0. Fragen Sie nach 2^4 mod 7, und es ist 2 – das ist die richtige: 2^3 = 8 ≡ 1 (mod 7), also 2^99 ≡ 1 und 2^100 ≡ 2, oder gleichwertig 2^6 ≡ 1 und 100 mod 6 = 4, was die ganze Frage auf 2^4 mod 7 reduziert.
Nichts an der Potenz ist falsch; der Rest ist es. Ein Double speichert dreiundfünfzig Bits, der nächste darstellbare Wert zu 2^100/7 liegt also um etwa 10^13 daneben, und ein Rest, berechnet als a − 7·floor(a/7), erbt einen Fehler, der viel größer ist als der Modul. Die richtige Methode lässt die Zahl nie wachsen: erst reduzieren, dann potenzieren, genau das tut die modulare Exponentiation in jeder kryptografischen Bibliothek, und es ist der Grund, warum RSA mit tausendbitigen Zahlen auf Hardware arbeiten kann, die dreiundfünfzig speichert. Es ist dieselbe Decke, die 2^53 zum letzten exakten Ganzzahlzähler macht.
Antwort
0
So lesen Sie sie
2^100 mod 7 auf dem Rechner – die Antwort der Maschine, nicht die der Arithmetik. Der zweite Link ist 2^6 mod 7 = 1, die Periode; der dritte ist die reduzierte Frage 2^4 mod 7 = 2, der wahre Wert.
Quelle
2^100 = 1267650600228229401496703205376 is exact in binary floating point, being a power of two, but the quotient by 7 has thirty significant digits and IEEE-754 binary64 carries only about sixteen, so a mod implemented as a − b·floor(a/b) returns a remainder taken from the rounded quotient
Im Rechner durchrechnen
Diese Links öffnen den passenden Rechner mit den bereits eingegebenen Zahlen dieser Aufgabe. Die Zeile darüber ist das, was der Bildschirm anzeigen sollte – prüfen Sie selbst.