Soon I will publish code that clearly demonstrates the kangaroo algorithm.
Baby-Step Giant-Step (BSGS):Solves g^x = h in a cyclic group of order n, or x in an interval of length N.
Precompute baby steps g^j for j = 0..m-1 in a hash table.
Compute giant steps h * (g^-m)^i and look for a match.
Time O(sqrt(N)), memory O(sqrt(N)).
Deterministic; works for any generic group.
Pollard's Kangaroo (Lambda) Algorithm:Solves g^x = h when x is known to lie in an interval [a,b].
Uses a tame kangaroo starting at g^b and a wild kangaroo starting at h.
Both jump by pseudorandom exponents; a collision reveals x.
Expected time O(sqrt(b-a)), memory O(1).
Probabilistic; needs a bounded interval.
Key difference: BSGS is deterministic and memory-heavy; Kangaroo is probabilistic, constant-memory, and interval-based.
MITM Algorithm:Large and small circle reduce range constantly till solution not found. (not public available, get all free RAM/VRAM, tested only with known PK, so far, MITM has not been used to solve any truly complex puzzle, need powerful hardware)