### Shanks baby-steps/giant-steps algorithm for finding the discrete log

We attempt to solve the congruence g^{x} ≡ b (mod m), where m > 1, gcd(g,m) = 1 = gcd(b,m).

The solution, if it exists, is unique (mod n), where n = ord_{m}g.

m has to satisfy m < 2^{32} – 2^{16} = 4294901760 here.

(See MP313 notes for the case where m is a prime.)

*Last modified 20th July 2004*

Return to main page