Babystep-Giantstep-Algorithmus

02.01.2018, 23:04

Mimi123

Babystep-Giantstep-Algorithmus

Meine Frage:
Hallo zusammen,
Ich hab hier eine Aufgabe. Das Thema ist diskrete Logarithmen. Ich sitze hier ein ganzen Tag lang schön und verstehe nicht wie man in den Paaren auf die rechte Seite kommt.

Meine Ideen:
Wenn ich wie definiert alpha * gamma^(-r) berechne komme ich da nicht auf zahlen wie zum Beispiel 404, sondern eher auf Brüche die durch die Potenz -r entsteht. Kann mir bitte jmd. Helfen.

02.01.2018, 23:12

sibelius84

Auf diesen Beitrag antworten »

Hallo Mimi123,

um $\begin{eqnarray*} \gamma^{-r} \end{eqnarray*}$ zu berechnen, solltest du wohl zuerst $\begin{eqnarray*} \gamma^{-1} \end{eqnarray*}$ bestimmen. Das Ganze nicht mit der herkömmlichen Bruch- und Potenzrechnung, sondern modulo 2017, indem du mit Hilfe des Erweiterten Euklidischen Algorithmus den ggT(5,2017) berechnest:

1.) 2017 = 403·5 + 2
2.) 5 = .... usw.

Damit kannst du die 1 als Summe von Vielfachen der Zahlen 5 und 2017 darstellen. Wenn du dann beide Seiten mit Rest durch 2017 teilst, siehst du ein Inverses von 5 mod 2017. Wenn du dieses noch mit r potenzierst, erhältst du $\begin{eqnarray*} \gamma^{-r} \end{eqnarray*}$ .

LG
sibelius84

03.01.2018, 11:35

Mimi123

Auf diesen Beitrag antworten »

Hallo und vielen Dank für die schnelle Antwort sibelius84 Freude

,
Warum berechnest du als erstes $\begin{eqnarray*} \gamma^{-1} \end{eqnarray*}$ ist das immer so und bleibt das für die gesamte Berechnung von r=0,1,2...,44? Damit meine ich warum du für r eins gewählt hast. Ich hab nun das Ergebnis 1 bekommen und Berechnet man $\begin{eqnarray*} \alpha =3+2017Z \end{eqnarray*}$ auch mit den euklidischen Algorithmus? Wenn ich das tun würde hätte ich $\begin{eqnarray*} \alpha =1 und \gamma =1 \end{eqnarray*}$ und ich kann mir nicht vorstellen auf werte zu kommen wie 404 verwirrt

Gruß
Mimi123

03.01.2018, 11:52

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Mimi123
Warum berechnest du als erstes $\begin{eqnarray*} \gamma^{-1} \end{eqnarray*}$

Diese Frage erledigt sich von selbst, wenn du einfach mal diesen Wert gemäß der Anleitung von sibelius84 berechnest. Denn dann kannst du die benötigten Werte via $\begin{align*} \alpha \cdot \gamma^{-r} = \alpha\cdot (\gamma^{-1})^r \end{align*}$ berechnen und kommst so zu der Liste 3, 404, 1291, 1065, 213, 446, 896, ...

Also nicht gleich am Anfang soviel rumdiskutieren und hinterfragen, sondern wirklich mal loslegen!

03.01.2018, 13:54

Mimi123

Auf diesen Beitrag antworten »

Ich komme auf $\begin{eqnarray*} 1=-2\cdot 2017+807\cdot 5 \end{eqnarray*}$ und das soll ich durch 2017 teilen.
Dann komme ich auf -2017+5* 807/2017 ich habe aber das Gefühl dass das so nicht gemeint ist verwirrt

03.01.2018, 14:12

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Mimi123
Ich komme auf $\begin{eqnarray*} 1=-2\cdot 2017+807\cdot 5 \end{eqnarray*}$

Richtig, und dies bedeutet dann ja $\begin{align*} 1\equiv 807\cdot 5\bmod 2017 \end{align*}$ .

Für $\begin{align*} \gamma=5 \end{align*}$ ist somit $\begin{align*} \gamma^{-1}=807 \end{align*}$ unsere gesuchte Inverse. Und damit kannst du dann rechnen:

$\begin{align*} 3 \end{align*}$
$\begin{align*} 3\cdot 807 = 2421\equiv 404\bmod 2017 \end{align*}$
$\begin{align*} 404\cdot 807 = 326028\equiv 1291\bmod 2017 \end{align*}$
$\begin{align*} 1291\cdot 807 = 1041837\equiv 1065\bmod 2017 \end{align*}$
usw.

03.01.2018, 18:23

Mimi123

Auf diesen Beitrag antworten »

Ich verstehe was du machst nur nicht warum. wie du oben erwähnt hattest ist $\begin{eqnarray*} (\gamma ^{-1} )^{r} \end{eqnarray*}$ aber bei dem Algorithmus wir nicht mit r potenziert und am Anfang des Algorithmus weiß ich nicht warum die drei alleine steht. verwirrt

03.01.2018, 20:11

HAL 9000

Auf diesen Beitrag antworten »

Kannst du nicht mal diesen winzigen Schritt selbständig durchdenken? unglücklich

Für die zu berechnenden Werte $\begin{align*} x_r = \alpha \gamma^{-r} = \alpha \left( \gamma^{-1} \right)^r \end{align*}$ ist der Startwert $\begin{align*} x_0 = \alpha \end{align*}$ und die restlichen kann man ja rekursiv über

$\begin{align*} x_r = \alpha \left( \gamma^{-1} \right)^{r-1}\cdot \gamma^{-1} = x_{r-1}\cdot \gamma^{-1} \end{align*}$

berechnen. Solltest du eigentlich wissen seit dem Moment, wo du geometrische Folgen in der Schule kennengelernt hast. unglücklich

Neue Frage »

Antworten »

Babystep-Giantstep-Algorithmus

Verwandte Themen