Baby-step-giant-step < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:29 Mo 25.04.2005 | | Autor: | Micha |
Hallo!
Also da ich vom Programmieren so gut wie keine Ahnung habe, brauche ich mal eure Hilfe! Folgendes Problem:
Ich soll den Diskreten Logarithmus von a bestimmen in einer vorgegebenen zyklischen Gruppe <g>.
Da gibt es zwar die brutale "Ausprobiermethode":
Logarithmus := function(a)
local i;
i:=0;
for i in [0..p] do
if [mm] g_hoch_n(g,i) [/mm] = a then return i;
fi;
od;
return false;
end;
Das Programm läuft übrigens in Kash, falls das jemand kennt.
aber die braucht mitunter seeeeehr lange, wenn ich ein großes p = Länge der Gruppe habe. (im Testbeispiel mit p = 42 Mio. hat das eine Laufzeit von ca 15 Minuten bei mir, wenn a ungünstig ist)
Als Hinweis zur besseren Programmierung wird die Baby-Step-Giant-Step-Methode vorgeschlagen, nur leider kann ich das irgendwie nicht umsetzen, was ich dazu im Netz finde...
Danke schonmal,
Gruß Micha 
|
|
|
![[]](/images/popup.gif){kind=small}
Implementierung in C