2.5.1: Diskrete Logarithmen - Shanks Algorithmus (baby-step giant-step)

Der Shank Algorithmus, auch "baby-step giant-step"-Algorithums genannt, berechnet für den diskreten Logarithmus
den Wert x aus &alphax ≡ &beta Mod p.


Ablauf des Algorithmus:
1.m = ⌈&radic(p-1)⌉
2.Für alle j mit 0 ≤ j < m:
Berechne &alphamj Mod p
Sortiere die Paare (j, &alphamj Mod p) nach der zweiten Komponente
4.Berechne &beta&alphai-1 Mod p für i mit 0 ≤ i < m
bis ein Wert &beta&alphai-1 Mod p mit &alphamj Mod p aus Schritt 2 übereinstimmt
5.Bilde aus den berechneten Werten x = log&alpha &beta = mj + i Mod p-1



source






3 Klassische Verfahren