Babystep-Giantstep-Algorithmus

Neue Frage »

Mimi123 Auf diesen Beitrag antworten »
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.
sibelius84 Auf diesen Beitrag antworten »

Hallo Mimi123,

um zu berechnen, solltest du wohl zuerst 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 .

LG
sibelius84
 
 
Mimi123 Auf diesen Beitrag antworten »

Hallo und vielen Dank für die schnelle Antwort sibelius84 Freude ,
Warum berechnest du als erstes 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 auch mit den euklidischen Algorithmus? Wenn ich das tun würde hätte ich und ich kann mir nicht vorstellen auf werte zu kommen wie 404 verwirrt
Gruß
Mimi123
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Mimi123
Warum berechnest du als erstes

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 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!
Mimi123 Auf diesen Beitrag antworten »

Ich komme auf 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
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Mimi123
Ich komme auf

Richtig, und dies bedeutet dann ja .

Für ist somit unsere gesuchte Inverse. Und damit kannst du dann rechnen:





usw.
Mimi123 Auf diesen Beitrag antworten »

Ich verstehe was du machst nur nicht warum. wie du oben erwähnt hattest ist aber bei dem Algorithmus wir nicht mit r potenziert und am Anfang des Algorithmus weiß ich nicht warum die drei alleine steht. verwirrt
HAL 9000 Auf diesen Beitrag antworten »

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


Für die zu berechnenden Werte ist der Startwert und die restlichen kann man ja rekursiv über



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



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »