Schnelle Exponentiation

15.02.2025, 16:53

Malcang

Auf diesen Beitrag antworten »

Schnelle Exponentiation

Hallo mal wieder smile

smile

ich habe hier im Skript einen Algorithmus zur schnellen Exponentiation gegeben. Es ist dieser:
[attach]58122[/attach]

Nun versuche ich das Beispiel nachzuvollziehen, dass ich hier habe. Berechnet werden soll $\begin{eqnarray*} 1292^{283} \pmod{2077} \end{eqnarray*}$ .

Es ist also
$\begin{eqnarray*} a_0 = 1292, p_0 = 1, n_0 = 283 \end{eqnarray*}$ .
Nun berechne ich $\begin{eqnarray*} p_1 = 1\cdot 1292, a_1 = (1292)^2 \pmod{2077}, n_1 = 141 \end{eqnarray*}$ .

Aber für den Ausdruck $\begin{eqnarray*} (1292)^2 \pmod{2077} \end{eqnarray*}$ brauche ich doch nun wieder schnelle Exponentiation verwirrt

verwirrt

Oder übersehe ich eine einfache Lösung?

15.02.2025, 17:29

HAL 9000

Auf diesen Beitrag antworten »

Nein, diese Quadratberechnung wird als normale Modulo-Multiplikation durchgeführt - wir wollen doch nicht in einen Zirkelschluss geraten. Augenzwinkern

Augenzwinkern

Man kann das Verfahren auch so beschreiben: Ausgehend von der Binärdarstellung $\begin{eqnarray*} m = \sum_{i=0}^r b_i 2^i \end{eqnarray*}$ des Exponenten modulo-multipliziert man diejenigen $\begin{eqnarray*} a^{2^i} \end{eqnarray*}$ miteinander, für die $\begin{eqnarray*} b_i=1 \end{eqnarray*}$ (also Einsziffer in der Binärdarstellung) ist. Im Laufe dieses Verfahrens werden die $\begin{eqnarray*} a^{2^i} \end{eqnarray*}$ durch iteriertes Quadrieren berechnet, d.h. basierend auf $\begin{eqnarray*} a^{2^i} = \left(a^{2^{i-1}}\right)^2 \end{eqnarray*}$ .

Wegen $\begin{eqnarray*} r= \left\lfloor \log_2(n)\right\rfloor \end{eqnarray*}$ sind dabei also "nur" $\begin{eqnarray*} O\left(\log(n)\right) \end{eqnarray*}$ Modulo-Multiplikationen nötig.

15.02.2025, 17:54

Malcang

Auf diesen Beitrag antworten »

Danke sehr HAL. Aber gibt es für diese Quadratberechnung wiederum einen Trick? Denn es heißt, man könne das nun "leicht" schriftlich durchführen.

15.02.2025, 18:54

HAL 9000

Auf diesen Beitrag antworten »

Von "leicht" kann keine Rede sein - es reduziert nur eben die Anzahl der nötigen Multiplikationen:

Es ist $\begin{eqnarray*} 283=[100011011]_2 \end{eqnarray*}$ , also insgesamt 5 Einsen in einer 9stelligen Binärzahl, macht demnach 5+9=14 nötige Multiplikationen - DAS allein ist mit "leicht" gemeint, etwa gegenüber der primitiven Methode mit 283 Multiplikationen.

------------------------------------------------------------------------------------------

Wenn du die Aufgabe wirklich schriftlich ohne jede Rechenhilfsmittel bewältigen sollst, dann kannst du alternativ auch anders vorgehen:

1) Zunächst Primfaktorzerlegung des Moduls (auch das kann schriftlich schon mal dauern): $\begin{eqnarray*} 2077 = 31\cdot 67 \end{eqnarray*}$

2) Getrennte Berechnung nach Primfaktormodulen - wenn es geht auch unter Nutzung des Kleinen Fermat:

$\begin{eqnarray*} 1292^{283} \equiv (-10)^{283} \equiv (-10)^{13} \equiv 22\bmod 31 \end{eqnarray*}$

$\begin{eqnarray*} 1292^{283} \equiv 19^{283} \equiv 19^{19} \equiv 39\bmod 67 \end{eqnarray*}$

3) Lösung des Kongrunzystems

$\begin{eqnarray*} x \equiv 22\bmod 31 \end{eqnarray*}$

$\begin{eqnarray*} x \equiv 39\bmod 67 \end{eqnarray*}$

bestimmen (Chinesischer Restsatz), ergibt $\begin{eqnarray*} x \equiv 642\bmod 2077 \end{eqnarray*}$ .

Ist viel Schreibaufwand, aber manuell vermutlich etwas schneller bewältigen als das oben - wobei man für die Teilaufgaben $\begin{eqnarray*} (-10)^{13}\bmod 31 \end{eqnarray*}$ sowie $\begin{eqnarray*} 19^{19}\bmod 67 \end{eqnarray*}$ durchaus ja auch die schnelle Exponentiation anwenden kann, mit deutlich kleineren Zahlen, wo die anstehenden Quadrierungen für gute Kopfrechner sogar schon bewältigbar sind. Augenzwinkern

Augenzwinkern

15.02.2025, 19:16

Malcang

Auf diesen Beitrag antworten »

Ok, danke HAL, das sehe ich ein.

Das ganze war mal eine Klausuraufgabe, daher dachte ich, ich übersehe einen Trick für's schriftliche Rechnen.
Mir fiele bloß noch ein, das Ganze über den chinesischen Restsatz zu lösen:
$\begin{eqnarray*} 1292^2 \equiv (-10)^2 \equiv 100 \equiv 7 \pmod{31} \end{eqnarray*}$
$\begin{eqnarray*} 1292^2 \equiv 19^2 \equiv 361 \equiv 26 \pmod{67} \end{eqnarray*}$

und zusammengesetzt erhalte ich dann $\begin{eqnarray*} 1292^2 \equiv 1433\pmod{2077} \end{eqnarray*}$ .

Wirklich einfacher finde ich das aber auch nicht.

Edit: Das hat sich gerade auf die Sekunde mit deinem Edit überschnitten Big Laugh

Big Laugh

Edit2: Ah, ich sehe, du hast die gesamte Aufgabe mit dem CRT betrachtet. Das ist natürlich auch möglich, jedoch lautete die Aufgabenstellung "mit schneller Exponentiation". Sicherlich geht deine Methode "noch schneller" Big Laugh

Big Laugh

15.02.2025, 19:27

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Malcang
Das ganze war mal eine Klausuraufgabe,

Wobei ich annehme, dass einfache Taschenrechner erlaubt waren? Na da kannst du doch die Einzelschritte $\begin{eqnarray*} x\cdot y\bmod 2077 \end{eqnarray*}$ mit "erst multiplieren, dann modulo" doch ganz flink berechnen, und bei dieser Aufgabe dann eben 14-mal.

Anzeige

15.02.2025, 19:41

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Zitat:

Original von Malcang
Das ganze war mal eine Klausuraufgabe,

Wobei ich annehme, dass einfache Taschenrechner erlaubt waren? Na da kannst du doch die Einzelschritte $\begin{eqnarray*} x\cdot y\bmod 2077 \end{eqnarray*}$ mit "erst multiplieren, dann modulo" doch ganz flink berechnen, und bei dieser Aufgabe dann eben 14-mal.

Nein, keine Taschenrechner erlaubt. Jedenfalls würde es mich wundern. Ich kenne die Aufgabe aus einer Altklausur und es waren noch nie Taschenrechner erlaubt.

15.02.2025, 19:47

HAL 9000

Auf diesen Beitrag antworten »

Oje ... hat man dann eine Stunde Zeit (oder noch mehr) für diese Aufgabe, oder wie? verwirrt

verwirrt

15.02.2025, 19:53

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Oje ... hat man dann eine Stunde Zeit (oder noch mehr) für diese Aufgabe, oder wie? verwirrt

verwirrt

Ich gehe nicht davon aus, die Klausur dauerte insgesamt 120 Minuten. Der Prof. ist aber auch leider nicht mehr an unserer Uni.

17.02.2025, 10:28

HAL 9000

Auf diesen Beitrag antworten »

Ich hab gerade mal im Selbstversuch getestet: Mit dem Originalmodul 2077 habe ich für eine solche Multiplikation zweier vierstelliger Zahlen gefolgt von einer Division mit Rest durch 2077 ca. 2,5 Minuten benötigt. Mit 14 multipliziert ergibt das 35 Minuten, dabei sind keine Zeiten für Überprüfungen einbezogen. Und da ich noch einer Generation entstamme, die die ersten 9 Schuljahre ohne Taschenrechner bewältigen musste, bilde ich mir auch ein, da auch gar nicht so schlecht im Kopfrechnen zu sein (wenn auch etwas aus der Übung).

Daher denke ich, dass eine Stunde Zeit für diese Aufgabe gewiss nicht zu hoch gegriffen ist. Es sei denn, sowas wird vorher exzessiv geübt, aber ich wüsste nicht, warum eine solche Fronarbeit im universitären Umfeld angestellt werden sollte.

17.02.2025, 12:27

willyengland

Auf diesen Beitrag antworten »

Vielleicht wäre der genaue Aufgabentext hilfreich?

17.02.2025, 12:37

HAL 9000

Auf diesen Beitrag antworten »

Die Aufgabe ist (s.o.): Berechne $\begin{eqnarray*} 1292^{283}\bmod 2077 \end{eqnarray*}$ .

Unklar waren die zur Verfügung stehenden Mittel - und wie ich Malcang verstanden habe: Keinerlei elektronische, d.h., nur Gehirn, Stift und Papier.

17.02.2025, 14:30

willyengland

Auf diesen Beitrag antworten »

Vielleicht stand da ja noch etwas dabei, z.B. Wie würden sie prinzipiell vorgehen?

17.02.2025, 14:56

HAL 9000

Auf diesen Beitrag antworten »

Ok: Kennst du eine Methode, die ohne rechentechnische Hilfsmittel signifikant schneller als die beiden vorgestellten Alternativen ist?

EDIT: Ach du meinst, dass man skizzieren soll, wie man vorgehen will, ohne konkret zu rechnen? Dann hätte uns Malcang aber ganz schön veralbert mit diesem Thread.

17.02.2025, 17:17

HAL 9000

Auf diesen Beitrag antworten »

Vielleicht noch ein kleiner Exkurs, wie man bei in Relation zum Modul $\begin{eqnarray*} m \end{eqnarray*}$ vergleichsweise großen Exponenten $\begin{eqnarray*} n \end{eqnarray*}$ diesen Exponenten "reduzieren" kann:

1) Sind $\begin{eqnarray*} a,m \end{eqnarray*}$ teilerfremd, so gilt bekanntlich $\begin{eqnarray*} a^{\lambda(m)}\equiv 1\bmod m \end{eqnarray*}$ , dabei ist $\begin{eqnarray*} \lambda \end{eqnarray*}$ die Carmichael-Funktion (welche im Fall von ungeraden Primfaktorpotenzen mit der Eulerschen Phi-Funktion übereinstimmt, sonst aber nur ein echter Teiler davon ist). Es folgt unmittelbar

$\begin{eqnarray*} a^n\equiv a^r\bmod m \end{eqnarray*}$ für $\begin{eqnarray*} n\equiv r\bmod \lambda(m) \end{eqnarray*}$ .

Im obigen Beispiel $\begin{eqnarray*} m=2077=31\cdot 67 \end{eqnarray*}$ ist $\begin{eqnarray*} \lambda(m)=\operatorname{kgV}(30,66) = 330 \end{eqnarray*}$ und somit $\begin{eqnarray*} 1292^n\equiv 1292^r\bmod 2077 \end{eqnarray*}$ für $\begin{eqnarray*} n\equiv r\bmod 330 \end{eqnarray*}$ . Nützt bei $\begin{eqnarray*} n=283 \end{eqnarray*}$ leider herzlich wenig, etwas größer sollte der Exponent also schon sein, damit man das nutzen kann.

2) Sind $\begin{eqnarray*} a,m \end{eqnarray*}$ nicht teilerfremd, so ist dennoch noch einiges möglich. Zunächst mal zerlegt man das Modul $\begin{eqnarray*} m=u\cdot v \end{eqnarray*}$ derart, dass $\begin{eqnarray*} a,u \end{eqnarray*}$ teilerfremd sind und der andere Faktor $\begin{eqnarray*} v \end{eqnarray*}$ nur Primteiler enthält, die auch in $\begin{eqnarray*} a \end{eqnarray*}$ enthalten sind (wenn auch ggfs. mit anderen Exponenten). Zunächst halten wir fest, dass dann $\begin{eqnarray*} v\mid a^r \end{eqnarray*}$ für genügend große $\begin{eqnarray*} r \end{eqnarray*}$ gilt, sei $\begin{eqnarray*} r_0 \end{eqnarray*}$ das kleinste dieser $\begin{eqnarray*} r \end{eqnarray*}$ (dieses $\begin{eqnarray*} r_0 \end{eqnarray*}$ lässt sich leicht aus den Primfaktorzerlegungeb von $\begin{eqnarray*} a \end{eqnarray*}$ und $\begin{eqnarray*} v \end{eqnarray*}$ ermitteln). Nun gilt (siehe 1)) $\begin{eqnarray*} a^{\lambda(u)}\equiv 1\bmod u \end{eqnarray*}$ und außerdem $\begin{eqnarray*} a^r\equiv 0\bmod v \end{eqnarray*}$ für alle $\begin{eqnarray*} r\geq r_0 \end{eqnarray*}$ , aus beiden zusammen folgt

$\begin{eqnarray*} a^n\equiv a^r\bmod m \end{eqnarray*}$ für $\begin{eqnarray*} n\equiv r\bmod \lambda(u) \end{eqnarray*}$ und $\begin{eqnarray*} r\geq r_0 \end{eqnarray*}$ .

Man kann das auch so formulieren, dass Folge $\begin{eqnarray*} \left( a^n\bmod m\right)_{n=0,1,\ldots} \end{eqnarray*}$ ab Index $\begin{eqnarray*} n=r_0 \end{eqnarray*}$ periodisch ist mit Periodenlänge $\begin{eqnarray*} \lambda(u) \end{eqnarray*}$ , die allerdings (abhängig von $\begin{eqnarray*} a \end{eqnarray*}$ ) nicht notwendig auch die kleinste Periodenlänge sein muss.

Beispiel: $\begin{eqnarray*} a=2 \end{eqnarray*}$ und $\begin{eqnarray*} m=100 \end{eqnarray*}$ , dann ist $\begin{eqnarray*} u=25,v=4 \end{eqnarray*}$ sowie $\begin{eqnarray*} \lambda(25)=20 \end{eqnarray*}$ und $\begin{eqnarray*} r_0=2 \end{eqnarray*}$ . Daraus folgt, dass $\begin{eqnarray*} 2^{20k+2} \end{eqnarray*}$ für alle $\begin{eqnarray*} k\geq 0 \end{eqnarray*}$ die beiden Endziffern $\begin{eqnarray*} 2^2 = 04 \end{eqnarray*}$ aufweist.

1) kann man übrigens als Spezialfall $\begin{eqnarray*} u=m,v=1 \end{eqnarray*}$ und damit dann $\begin{eqnarray*} r_0=0 \end{eqnarray*}$ auffassen.

17.02.2025, 21:27

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
EDIT: Ach du meinst, dass man skizzieren soll, wie man vorgehen will, ohne konkret zu rechnen? Dann hätte uns Malcang aber ganz schön veralbert mit diesem Thread.

Nein, das war so nicht gemeint. Es ging also ganz konkret um das Rechnen.

18.02.2025, 12:28

HAL 9000

Auf diesen Beitrag antworten »

Hatte ich auch nicht wirklich angenommen. Es bleibt eine seltsame Klausuraufgabe, die aus dem (doppeldeutig gemeinten) Zeitrahmen fällt. Mit erlaubtem TR und auf 15min kalkuliert wäre sie Ok.

P.S.: In Python übrigens eine einzige Anweisung pow(1292,283,2077), und man muss dazu nicht mal eine zusätzliche Bibliothek importieren...

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »