Modulo-Rechnung mit Square/Multiply?

23.10.2013, 18:08

Brummbär

Modulo-Rechnung mit Square/Multiply?

Hallo,

Wie berechnet man große Modulo-rechnungen wie etwa

$\begin{eqnarray*} 405^(12*5*2013) mod 17 \end{eqnarray*}$ ?

Ich hab mir grad mal die sog Square&Multiply Methode angesehen, komme mit der aber nicht weiter (v.a. wegen 2013). Sieht auch irgendwie zu umständlich aus...

Wäre echt nett wenn mir jemand weiterhilft!

23.10.2013, 18:27

Captain Kirk

Auf diesen Beitrag antworten »

Hallo,

ich vermute mal es soll
$\begin{eqnarray*} 405^{12\cdot 5\cdot 2013} \mod 17 \end{eqnarray*}$ berechnet werden.

Reduziere zuerst mal die Basis modulo 17, am besten verwendest hier den Umstand, dass für ungerade n die Zahlen $\begin{eqnarray*} \-frac {n-1}{2}, \ldots , \frac{n-1}{2} \end{eqnarray*}$ alle Restklassen repräsentieren.

Auf den Exponenten kann man den kleinen Satz von Fermat, falls bekannt, anwenden.

Auf das was dabei rauskommt dann square&multiply loslassen.

23.10.2013, 18:41

Brummbär

Auf diesen Beitrag antworten »

Die einzelnen Schritte sind mir leider unbekannt / unklar..

Ich hatte gehofft irgendwie weiterzukommen mit

$\begin{eqnarray*} (405^2)^2)^3)^5)^2013) \end{eqnarray*}$ und 2013 noch weiter zerlegen - so weit wie möglich..

und dann

405^2 mod 17 = a
a^2 mod 17 = b
b^3 mod 17 = c
etc.

Geht das irgendwie? Ich muss mich leider sehr schnell in den Bereich Zahlentheorie einarbeiten und habe nicht sehr viel Zeit um die Grundlagen zu lernen verwirrt

23.10.2013, 18:52

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

405^2 mod 17 = a
a^2 mod 17 = b
b^3 mod 17 = c etc.

Natürlich kann man das machen. Ist auch nicht wesentlich verschieden zu square&multiply.

Und selbst dafür ist es massiv anzuraten 405,a,b,c etc. mod 17 zu reduzieren auf einen der Standardrepräsentanten (was übrigens ein absolutes Standardverfahren ist.)

24.10.2013, 09:38

Brummbär

Auf diesen Beitrag antworten »

Zitat:

Original von Captain Kirk

Zitat:

405^2 mod 17 = a
a^2 mod 17 = b
b^3 mod 17 = c etc.

Hierzu dann die von dir oben genannte Formel?

$\begin{eqnarray*} \frac {n-1}{2}, \ldots , \frac{n-1}{2} \end{eqnarray*}$

Was bedeutet das und wie soll ich das anwenden, um auf einen Standardrepräsentanten zu reduzieren?

24.10.2013, 16:37

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Brummbär
Hierzu dann die von dir oben genannte Formel?

$\begin{eqnarray*} \frac {n-1}{2}, \ldots , \frac{n-1}{2} \end{eqnarray*}$

Gemeint war sicher

$\begin{eqnarray*} -\frac {n-1}{2}, \ldots , \frac{n-1}{2}\qquad (*) \end{eqnarray*}$

für wie gesagt nur ungerade $\begin{eqnarray*} n \end{eqnarray*}$ . Mit Operation

$\begin{eqnarray*} x \bmod n = x - n\cdot \left\lfloor \frac{x}{n} \right\rfloor \end{eqnarray*}$

unter Benutzung der Gaußklammer (=Abrundung zur nächsten ganzen Zahl) $\begin{eqnarray*} \lfloor \ldots \rfloor \end{eqnarray*}$ kann man den Rest zunächst in den Bereich $\begin{eqnarray*} 0,1,\ldots,n-1 \end{eqnarray*}$ bringen. Bei entstehenden Werten $\begin{eqnarray*} >\frac{n}{2} \end{eqnarray*}$ muss man dann nochmals $\begin{eqnarray*} n \end{eqnarray*}$ subtrahieren, um in den Bereich (*) zu kommen.

Neue Frage »

Antworten »

Modulo-Rechnung mit Square/Multiply?

Verwandte Themen