Modulo bei grossen Zahlen: Wie kann ich es aufteilen, dass ich es mit einem Taschenrechner ausrechnen kann?

Question

Aufgabe:

532¹⁰⁰ mod 919

Problem/Ansatz:

Ich möchte dies gerne auf kleine Zahlen runterbringen, sodass ich es dann mit dem Taschenrechner ausrechnen kann. Wie geht man hier vor? Mein Vorgehen, war folgendes:

532¹⁰⁰ mod 919

= (532^25 mod 919 * 532^25 mod 919 * 532^25 mod 919 * 532^25 mod 919) mod 919

Gibt es hier einen einfacheren Weg?

Answer 1

Hallo,

Gibt es hier einen einfacheren Weg?

Ja - stelle diese Tabelle auf:$$\begin{array}{rrr}a_i& b_i& c_i\\\hline 532& 100& 1\\ 891& 50& 1\\ 784& 25& 1\\ 764& 12& 784\\ 131& 6& 784\\ 619& 3& 784\\ 857& 1& 64\\ &0& {\color{red}627}\\\end{array}$$es gilt stets: $$532^{100} \equiv a_i^{b_i} \cdot c_i \mod 919 \quad \forall i \in \mathbb N_0$$Das \(i\) ist der Index der Zeile. Auf die nächste Zeile kommt man mit$$a_{i+1} \equiv a_{i}^2 \mod 919 \\ b_{i+1} = \lfloor b_i/2\rfloor \\ c_{i+1} \equiv c_i \cdot a_{i}^{b_{i}-2b_{i+1}}\mod 919$$Bem.: der Ausdruck im Exponenten von \(a_i^{\dots}\) kann natürlich nur 0 oder 1 sein. Es geht hier nur darum, das \(c_i\) nochmal zu multiplizieren oder nicht.

Die Tabelle endet, sobald bei dem \(b_i\) der aktuellen Zeile eine 0 erscheint. Das Ergebnis ist dann das \(c_i\).