Baby-Step Giant-Step
The BSGS algorithm splits the discrete logarithm x=im+j (with m=ceil(√n)) into two steps: precompute g^j (baby steps), then search h*(g^(-m))^i (giant steps).
Purpose
To solve discrete logarithms with a time-space tradeoff at O(√n) complexity.
Mechanism
Let m=ceil(√n). Baby steps: compute and store {g^j : 0≤j<m}. Giant steps: for i=0,1,... compute h*g^(-im) and look it up in the table; on a match, x=im+j. Time O(√n), space O(√n).
Use cases
- Discrete logarithm solving
- Cryptanalysis
- Number-theoretic algorithms