Aufwand für die Berechnung der modularen Quadratwurzel

03.07.2005, 20:18	tuxracer	Auf diesen Beitrag antworten »
Aufwand für die Berechnung der modularen Quadratwurzel Hi, ich grüble z.Z. über den Aufwand für das Lösen einer modularen Quadratwurzel. Ich habe eine Gleichung, z.B. $\begin{eqnarray} x^2 \equiv 3 (mod 11) \end{eqnarray}$ gegeben. Die Lösung ist dann wohl ein munteres Ratespiel durch Einsetzen. Jetzt überlege ich gerade welchen Aufwand das Einsetzen erfordert, also wieviele x muss ich im schlimmsten Fall einsetzen? Die Lösung scheint bei einer Gleichung der Form $\begin{eqnarray} x^2 \equiv z (mod n) \end{eqnarray}$ 2^n Versuche zu sein. Ein Komilitone meinte "Es sind 2^n, weil wir 4! Versuche haben!". Ich kann das Ganze nur noch nicht so ganz nachvollziehen. Aber warum sollte 4 für alle mod n zutreffen? Das ganze ist ja zyklisch. Es muss also prinzipiell mit einer endlichen Anzahl von Versuchen möglich sein die Lösung durch Einsetzen zu bestimmen. Ich dachte bis jetzt immer meine obere Schranke für die Anzahl der Versuche müsste direkt n sein. Ich kann mir nicht ganz herleiten wieso es 2^n Versuche sind. Auch mit der Aussage "weil wir 4! Versuche haben" komme ich nicht so ganz klar. Weshalb 4? n! würde für mich mehr Sinn ergeben. Zuerst habe ich n Möglichkeiten irgendein x einzusetzen und dann immer weniger, bis ich alle durchprobiert habe. Ich hatte schonmal versucht mir das Ganze mit ein paar Gleichungen herzuleiten, da bin ich aber nicht sehr weit gekommen. Bei kleinen n hatte ich immer <n Versuche benötigt. Hat da jemand eine Idee??
03.07.2005, 20:34	AD	Auf diesen Beitrag antworten »
Du hast vollkommen recht, und wegen $\begin{eqnarray} x^2=(-x)^2 \end{eqnarray}$ musst du sogar nur $\begin{eqnarray} x=0,1,\ldots,\left\lfloor\frac{n}{2}\right\rfloor \end{eqnarray}$ untersuchen. So genau kenne ich mich nicht aus, was der effizienteste Algorithmus hier ist, aber für Nichtprimzahlen n geht es durchaus schneller als n/2.
03.07.2005, 20:57	tuxracer	Auf diesen Beitrag antworten »
Und wenn n zusammengesetzt ist, ist floor(n/2) trotzdem meine Obergrenze?
03.07.2005, 21:02	AD	Auf diesen Beitrag antworten »
Ganz klar: Ja!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »