[ZT] n^k mod p = k ---- Wie?

15.12.2016, 12:39

Aldebaran

Meine Frage:
Gegeben ist: $\begin{eqnarray*} n^{k} = k (mod p) \end{eqnarray*}$

Kurz gefragt, gibt es einen effizienten Weg, k zu berechnen, falls überhaupt eins existiert?

Um es zu verdeutlichen hab ich ein kleines Programm (in IDLE für Python 3.5) geschrieben:

code:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:	>>> n = 7 >>> m = 100 >>> for k in range(m-1, 0, -1): if nk % m == k: print (n, k) break 7 43 >>> print (743) 2183814375991796599109312252753832343

Dieses Beispiel sucht das größte k, für welches die Kongruenz gilt. Wenn man aber große Moduli hat oder mehrere Werte in Folge berechnen will, benötigt diese Methose unsäglich viel Zeit.

Meine Ideen:
So richtig hab ich noch keine Idee. Ich dachte erst an Logarithmen, hab sie aber auch schnell wieder verworfen. Außerdem kam mir Pollards Rho Algorithmus für Diskrete Logarithmen in den Sinn. Das hat mich aber auch nicht weit gebracht.

Hätte von euch jemand eine Idee?

Zwei Beiträge zusammengefasst. Steffen

Ich hab gesehen, dass ich in der Beschreibung p und im Code m für den Modulus verwendet hab. Außerdem hab ich vergessen zu erwähnen, dass der Exponent k kleiner als der Modulus sein soll. Das geht aus dem Code hervor, fehlt aber in der Beschreibung.

15.12.2016, 13:15

HAL 9000

Auf diesen Beitrag antworten »

$\begin{align*} n,p \end{align*}$ sind gegeben und $\begin{align*} k \end{align*}$ gesucht? Und $\begin{align*} p \end{align*}$ ist prim sowie $\begin{align*} p\not\mid n \end{align*}$ ? verwirrt

Ziemlich ungewöhlich, dass $\begin{align*} k \end{align*}$ sowohl in Exponent als auch Potenzerergebnis auftaucht. Eins kann man zumindest feststellen:

Für $\begin{align*} f(j):=(n^j-j)\bmod p \end{align*}$ gilt $\begin{align*} f(j+p-1) \equiv n^{j+p-1}-(j+p-1)\equiv n^j-j+1 = f(j)+1\bmod p \end{align*}$ und folglich $\begin{align*} f(j+m(p-1))\equiv f(j)+m\bmod p \end{align*}$ .

Zu gegebenen $\begin{align*} j=0,1,\ldots,p-2 \end{align*}$ sind also alle Werte $\begin{align*} k=j+m(p-1) \end{align*}$ mit $\begin{align*} m\equiv -f(j)\bmod p \end{align*}$ Lösung deiner Gleichung $\begin{align*} f(k)=0 \end{align*}$ - und letztlich nur die!

Ist $\begin{align*} p \end{align*}$ allerdings nicht prim (wie in deinem Beispiel $\begin{align*} p=100 \end{align*}$ ), dann ist es etwas komplizierter.

15.12.2016, 13:23

Aldebaran

Auf diesen Beitrag antworten »

Meine Annahme ist, dass man für komposite Moduli die Primfaktoren dessen betrachtet und dann den Chinesischen Restsatz anwendet.

15.12.2016, 13:28

HAL 9000

Auf diesen Beitrag antworten »

Primfaktoren allein wird nicht reichen, allenfalls Primfaktorpotenzen.

15.12.2016, 13:35

Aldebaran

Auf diesen Beitrag antworten »

Wenn Modulus = 100, dann also 2^2 = 4 und 5^2 = 25 betrachten....

16.12.2016, 11:16

Aldebaran

Auf diesen Beitrag antworten »

Ich hab das mal mit den Primfaktorpotenzen probiert, zumindest so wie ich mir das ausgemalt hab. Wahrscheinlich war das alles andere als richtig verwirrt

Ich hab dazu mein Python-Code etwas geändert:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:

def expmod(n, m):
    for k in range(m-1, 0, -1):
        if pow(n, k, m) == k:
            return k
    return -1

#
MOD = 10**2
M1 = 2**2
M2 = 5**2

b = 7
print (expmod(b, MOD))
print (expmod(b, M1))
print (expmod(b, M2))

Als Ergebnis bekomme ich

code:
1: 2: 3:	43 3 -1

angezeigt. Und ab hier weiß ich nicht so recht weiter verwirrt

16.12.2016, 11:44

HAL 9000

Auf diesen Beitrag antworten »

Weißt du eigentlich, was du da tust?

Wenn du Lösungen $\begin{align*} k \end{align*}$ von $\begin{align*} n^k = k\mod m \end{align*}$ suchst, und das auf die Primfaktorpotenzen von $\begin{align*} m \end{align*}$ herunterbrechen willst, dann musst du bei Primfaktorzerlegung $\begin{align*} m = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot \ldots\cdot p_r^{\alpha_r} \end{align*}$ nicht nur einfach die Kongruenzen

$\begin{align*} n^k = k\mod p_j^{\alpha_j} \end{align*}$ für $\begin{align*} j=1,2,\ldots,r \end{align*}$

nach irgendwelchen Lösungen $\begin{align*} k \end{align*}$ abklopfen, sondern nach solchen $\begin{align*} k \end{align*}$ , die gleichzeitig (!) alle $\begin{align*} r \end{align*}$ Kongruenzen lösen, d.h. für $\begin{align*} j=1,2,\ldots,r \end{align*}$ ! Unterschiedliche $\begin{align*} k \end{align*}$ für unterschiedliche $\begin{align*} j \end{align*}$ nützen in Bezug auf das Originalproblem $\begin{align*} n^k = k\mod m \end{align*}$ rein gar nichts. unglücklich

16.12.2016, 12:26

Aldebaran

Auf diesen Beitrag antworten »

Wow, das war peinlich Finger2

ich gehe das Ganze noch mal durch und melde mich dann -hoffentlich mit nicht ganz so viel Blödsinn- wieder

Neue Frage »

Antworten »

[ZT] n^k mod p = k ---- Wie?

Verwandte Themen