Wie kann man bei enr hohen Zahl die letzten beiden ziffern berechnen?

Question

zb 2^1234? wie kann man die letzten beiden ziffern berechnen?

Answer 1

um bei einer hohen Zahl wie zum Beispiel \( 2^{1234} \) die letzten beiden Ziffern zu berechnen, muss man in den Restklassenring modulo \( 100 \) übergehen.

In diesem kann dann mit Hilfe der sogenannten "schnellen Exponentiation" gerechnet werden und binnen weniger Milli- bis Mikrosekunden ergeben sich die letzten beiden Ziffern der Zahl \(2^{1234}\).

MfG

Mister

PS: Die schnelle Exponentiation ist also wahrlich eine schnelle Exponentiation. Bei genügend Speicherkapazität, mit anderen Worten 1234 Bits, kann die Zahl \( 2^{1234} \) auch im Ring der ganzen Zahlen berechnet werden. Dies dauert nicht wesentlich länger als modulo 100 zu rechnen.

Comments

abe rich meine mit dem taschenrechner?

und wieso gerade modulo 100?

---

Warum wohl modulo 100?

Answer 2

λ bezeichne die Carmichaelfunktion, φ die eulersche Phi-Funktion

Dann ist

%%\lambda (100)=kgV(\varphi (4),\varphi(25))=20$$

Also ist

$$2^{1234}=2^{20\cdot 61 +14}\equiv 2^{14} = 2^{10}\cdot 2^4=1024\cdot 16 \equiv 24 \cdot 16\equiv 84 \mod 100$$, d.h. die letzten beiden Ziffern sind 84