Pollard-Rho-Verfahren (diskrete Logarithmen)

07.01.2018, 15:00	Mimi123	Auf diesen Beitrag antworten »
Pollard-Rho-Verfahren (diskrete Logarithmen) Meine Frage: Hallo zusammen, ich möchte die Aufgabe $\begin{eqnarray} 5^{x}\equiv 3 mod 2017 \end{eqnarray}$ mit dem Pollard?rho?Verfahren berechnen. Als Zufallszahl, wähleich $\begin{eqnarray} x_{0} =1023 \end{eqnarray}$ und $\begin{eqnarray} y_{0} =0 \end{eqnarray}$ . Dann hab ich meine Menge in drei zueinander disjunkten Mengen aufgeteilt: $\begin{eqnarray} G_{1} =\left\{ 1,..,672\right\}, G_{2} =\left\{ 673,..,1344\right\}, G_{3} =\left\{ 1345,..,2016\right\} \end{eqnarray}$ . Nun möchte ich $\begin{eqnarray} \beta_{i+1} =f(\beta_{i})=f( \gamma^{x_{i} } \alpha^{y_{i}} ) \end{eqnarray}$ lösen. Wie $\begin{eqnarray} x_{i+1} ,y_{i+1} und f(\beta ) \end{eqnarray}$ definiert ist, hab ich angehängt. Meine Ideen: Also hab ich angefangen zu rechnen, $\begin{eqnarray} f(\gamma^{1023} \alpha ^{0} )= f(\gamma^{1023} ) \end{eqnarray}$ Nun kann ich aber nicht weiter rechnen, weil wenn ich $\begin{eqnarray} 5^{1023} \end{eqnarray}$ weil mein Taschenrechner nicht solch eine große Zahl ausgeben kann. Gibt es eine Alternative dafür oder ist meine Vorgehensweise einfach falsch?
07.01.2018, 15:08	forbin	Auf diesen Beitrag antworten »
Musst du das nicht ohnehin in der entsprechenden Restklasse berechnen?
07.01.2018, 15:24	Mimi123	Auf diesen Beitrag antworten »
Ich bin ja noch in der Restklasse da die Restklasse 2017 ist oder nicht?
07.01.2018, 16:28	tatmas	Auf diesen Beitrag antworten »
Die arbeitest hier im Ring modulo 2017. Du bist hier nie nicht im Restklassenring, daher ist auch jede Rechnung modulo 2017 zu machen. Auch gilt generell $\begin{eqnarray} x^{\frac{p-1}{2}} = \pm 1 \mod p \end{eqnarray}$ (außer für x=0.) Und längere Exponenten berechnet man in aller Regel mit square-and-multiply.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »