Fixpunkte bei modularem Potenzieren [Zahlentheorie]

17.06.2013, 22:53

Stefanm

Fixpunkte bei modularem Potenzieren [Zahlentheorie]

Meine Frage:
Mit dem Hintergrund RSA beschäftigen mich zur Zeit die Eigenschaften von modularen Potenzen. Dabei bin ich auf folgenden Umstand gestoßen, den ich mir nicht erklären kann, vielleicht kann mich jemand in die richtige Richtung schubsen?
Betrachtet man $\begin{eqnarray*} x^{13} mod 77 \end{eqnarray*}$ und setzt für x der Reihe nach die Zahlen von 2 bis 76 ein, dann ergeben sich zyklisch Fixpunktgruppen von drei Elementen, die jeweils um die Vielfachen von 11 angeordnet sind, also bei 10,11,12 und 21,22,23 und 32,33,34 usw. Wie kann man das Auftreten dieser Gruppen aus dem Exponenten 13 und dem Modul 77 erklären?

Meine Ideen:
Mir fehlt noch die richtige Idee, außer dass 11 ein Primfaktor des Moduls ist (allerdings was ist dann mit dem anderen Primfaktor 7?). Die Wiederholfrequenz $\begin{eqnarray*} \phi(77)=60 \end{eqnarray*}$ bringt mich bisher auch nicht weiter... Bräuchte mal einen Denkanstoss...

Vielen Dank!!!

17.06.2013, 23:23

Captain Kirk

Auf diesen Beitrag antworten »

Hallo,

es ist $\begin{eqnarray*} 10 \equiv 21\equiv 32 \equiv -1\mod 11 \end{eqnarray*}$
hoch 13 ist es wieder -1.
Für die anderen Fälle analog.
Und $\begin{eqnarray*} x^{13} = x^{2\varphi(7)+1}\equiv x \mod 7 \end{eqnarray*}$
Dann chin. Restsatz drauflos lassen.

19.06.2013, 11:08

Stefanm

Auf diesen Beitrag antworten »

Hallo,

super, vielen Dank für den Tipp. Das beudetet dann für mein Beispiel wegen ch. Restsatz, dass $\begin{eqnarray*} x^{13} = x mod 77 \equiv (x^{13} =x mod 7 \wedge x^{13} = x mod 11) \end{eqnarray*}$ , oder?
Muss ich noch mal durchrechnen, ergibt aber Sinn!

Vielen Dank für Deine Hilfe!

20.06.2013, 10:48

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Stefanm
super, vielen Dank für den Tipp. Das beudetet dann für mein Beispiel wegen ch. Restsatz, dass $\begin{eqnarray*} x^{13} = x mod 77 \equiv (x^{13} =x mod 7 \wedge x^{13} = x mod 11) \end{eqnarray*}$ , oder?

Ja, stimmt so, du solltest aber beachten, dass für eine Primzahl r jede Potenz $\begin{eqnarray*} x^k \end{eqnarray*}$ mit einem nicht(!) durch r-1 teilbaren k>0, prinzipiell zu

$\begin{eqnarray*} x^{k \mod (r-1)} \end{eqnarray*}$

vereinfacht werden kann... Speziell deine Bedingung mod 7 fällt somit ganz weg, was dann auch die eigentliche Erklärung für das eingangs beschriebene Phänomen darstellt... Augenzwinkern

Neue Frage »

Antworten »

Fixpunkte bei modularem Potenzieren [Zahlentheorie]

Verwandte Themen