Baby-step Giant-step (Shanks, 1971): solve g^x≡h (mod p). Set m=⌈√(p-1)⌉. Baby steps: compute g^j for j=0,...,m-1. Giant steps: compute h·(g^{-m})^i for i=0,...,m-1. Match at (i,j) gives x=im+j. O(√p) time and space.
How to Use
Enter g, h, p:
- x: Solution g^x≡h
- Baby: Precomputed table
- Giant: Search table
How It Works
Write x=im+j. Then g^{im+j}=h, so g^j=h·g^{-im}. Precompute all g^j (baby steps). Then check h·g^{-im} (giant steps) against the table. First match gives x.
Time-Space Tradeoff
BSGS uses O(√p) memory for the baby step table. This is the classic time-space tradeoff: without the table, brute force takes O(p). With O(√p) space, we reduce to O(√p) time. Often the practical limit is memory, not time.
Step-by-Step Instructions
- 1Enter base g.
- 2Enter target h.
- 3Enter prime p.
- 4Compute baby/giant steps.
- 5Find match.