Shanks baby-steps/giant-steps algorithm for finding the discrete log
We attempt to solve the congruence gx ≡ b (mod m), where m > 1, gcd(g,m) = 1 = gcd(b,m).
The solution, if it exists, is unique (mod n), where n = ordmg.
m has to satisfy m < 232 – 216 = 4294901760 here.
(See MP313 notes for the case where m is a prime.)
Last modified 20th July 2004
Return to main page