Dezimalstellen mit Modulorechnung

05.02.2010, 11:53

Alid

Dezimalstellen mit Modulorechnung

Hallo,

wenn ich die letzten drei Dezimalstellen der Zahl 7^29 berechnen soll, dann weiß ich ja, dass ich selbige Modulo 1000 betrachten muss. Nun haben wir in unserer Vorlesung die Zahl 7^29 in 7^16, 7^8, 7^4 und 7^1 aufgeteilt und damit weitergerechnet. Der Weg im Allgemeinen ist mir klar, nur warum haben wir ausgerechnet die 16,8,4 und 1 als Potenzen gewählt? Hat das einen Zusammenhang mit der 1000? Oder könnte ich x-beliebige 4 Potenzen wählen, die nur den/die gleichen Teiler haben?

05.02.2010, 12:00

Auf diesen Beitrag antworten »

Das hat was mit effizienter Berechnung zu tun: Es ist

$\begin{eqnarray*} 7^4= (7^2)^2 \end{eqnarray*}$

$\begin{eqnarray*} 7^8 = (7^4)^2 \end{eqnarray*}$

$\begin{eqnarray*} 7^{16} = (7^8)^2 \end{eqnarray*}$

allgemein

$\begin{eqnarray*} 7^{2^{n+1}} = \left(7^{2^n} \right)^2 \end{eqnarray*}$ .

So kann man durch einfaches Quadrieren (und nachgeschobenes $\begin{eqnarray*} \bmod m \end{eqnarray*}$ )nacheinander die Reste $\begin{eqnarray*} 7^{2^n} \bmod m \end{eqnarray*}$ relativ schnell berechnen. Und bei beliebigen natürlichen Exponenten zerlegt man diesen Exponenten erstmal in eine Summe solcher Zweierpotenzen - kurz auch Binärdarstellung genannt - um dann diese vorberechneten Reste $\begin{eqnarray*} 7^{2^n} \bmod m \end{eqnarray*}$ nutzen zu können, hier in deinem Beispiel

$\begin{eqnarray*} 29 = 2^4 + 2^3 + 2^2 + 2^0 = [11101]_2 \end{eqnarray*}$ .

12.02.2010, 07:33

addor

Auf diesen Beitrag antworten »

RE: Dezimalstellen mit Modulorechnung

Zitat:

Original von Alid
wenn ich die letzten drei Dezimalstellen der Zahl 7^29....

Was, bitte sehr, hat jetzt das mit Dezimalstellen zu tun?

Neue Frage »

Antworten »

Dezimalstellen mit Modulorechnung

Verwandte Themen