Algorithmus gesucht < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo Zusammen,
Kennt jemand die Bezeichnung für diesen Algorithmus?
[mm]\begin{array}{l}
\texttt{compute }\left(\frac{a}{p}\right);\\
\textbf{if }\left(\frac{a}{p}\right)=-1\textbf{ then}\\
\qquad\textbf{return }\texttt{``$a\in NQ_p$''};\\
\textbf{else}\\
\qquad\texttt{choose }c\texttt{ at random from }Z_p^{\*};\\
\qquad\textbf{if }\left(\frac{c^2-a}{a}\right)=-1\textbf{ then}\\
\qquad\qquad\texttt{compute }\gcd\left(X^{\frac{p-1}{2}}-1,(X-c)^2-a\right);\\
\qquad\qquad\texttt{the result ist }X-r;\\
\qquad\qquad\textbf{return }\sqrt{a}=\pm(c+r);
\end{array}
[/mm]
Grüße
Karl
[ P.S. Ich habe diese Frage auch ![[]](/images/popup.gif) im Usenet gestellt. ]
|
|
|
