wurzel aus modulo, wie ziehe ich wurzel aus modulo

Question

gegeben ist:

m ≡ x^a   mod n

man kann nun x berechnen, wenn man die lineare Diophantische Gleichung:

a * y - k * φ(n) = 1   

löst, denn es gilt

m ≡ m^{a * y}  ≡ m^{k * φ(n) + 1} mod n

damit ist:

x ≡ m^y modulo n

die Lösung.

Dieser Lösungsweg "funktioniert" aber nur, wenn a ungerade ist, denn

eine lineare Diophantische Gleichung ist nur lösbar, wenn der (ggT) der 

Koeffizienten (der Faktoren vor den Variablen)  ein Teiler der konstanten Zahl ist.

Bei ungeraden Koeffizienten ist der (ggT) 1 und damit ein Teiler der konstanten Zahl 1.

Bei geraden Koeffizienten ist der (ggT) 2 und damit kein Teiler der konstanten Zahl 1.

 

Frage. Wie kann man x ermitteln, wenn der Exponent eine gerade Zahl ist?

Answer 1

Für gerades a schreibe es in der Form $$a= 2^k b, \text{ wobei } ggT(2,b)=1$$. Mit deinem Verfahren kannst du $$x^{2^k}$$ berechnen. Damit musst du nur noch Quadratwurzeln ziehen, dafür gibt es spezielle Verfahren, z.B. https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm bzw. für $$p\equiv 3 \mod 4$$ lassen sich die Wurzeln direkt hinschreiben. P.S. Der lösungsweg funktioniert auch für einige andere a nicht. Es muss a teilerfremd zu phi(n) sein.

Comments

Sorry, dachte auf den ersten Blick, die Antwort verstanden zu haben. Bei genauerer Überlegung geht das irgend wie zu schnell.

 

Ich komme von   _x2^k    nicht auf    x ≡ w² mod n  (die modulare Quadratwurzel aus w soll ja schlussendlich x ergeben)

Kannst Du bitte etwas ausführlicher erklären, wie man auf w kommt?

---

$$\sqrt{x^{2^k}}= \pm x^{2^{k-1}}$$, d.h. man erhält x durch ziehen von k Quadratwurzeln.

---

O.K. danke, alles klar jetzt. Hatte nicht genau "hingelesen".

 

Du hast ja schon gemerkt, dass die Frage nach der Laufzeit von mir ist. Und Du vermutest richtig, es geht um Kryptologie. 

Mir ist aufgefallen dass das Problem des diskreten Logarithmus

m ≡ m' ^x  mod n

gut untersucht und beschrieben ist.

 

Über das Problem:

m ≡ x ^a   mod n

in Verbindung mit Kryptologie habe ich nichts brauchbares finden können.

Daher interessiert mich die Anzahl Iterationen für das Wurzelziehen, um die "echte" Laufzeit bei gegebenen MIPS berechnen zu können.

---

O.K. danke, alles klar jetzt. Hatte nicht genau "hingelesen".

 

Du hast ja schon gemerkt, dass die Frage nach der Laufzeit von mir ist. Und Du vermutest richtig, es geht um Kryptologie. 

Mir ist aufgefallen dass das Problem des diskreten Logarithmus

m ≡ m' ^x  mod n

gut untersucht und beschrieben ist.

 

Über das Problem:

m ≡ x ^a   mod n

in Verbindung mit Kryptologie habe ich nichts brauchbares finden können.

Daher interessiert mich die Anzahl Iterationen für das Wurzelziehen, um die "echte" Laufzeit für die Lösung dieses Problems bei gegebenen FLOP's berechnen zu können.

---

Damit suchst du eine Nullstelle des polynoms $$X^a-m \in \mathbb F_p$$ (man kann den allgemeinen Fall wie beim DL per chin. Restsatz darauf reduzieren). Zum einen kann es mehrere Nullstellen geben, was für Verschlüsselungsanwendeungen nicht wirklich ideal ist, zum Anderen gibt es Methoden Polynome über endlichen Körpern schnell zu faktorisiren: https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields