if you use bsgs(kangaroo)
What is bsgs(kangaroo)
In the cryptic world of
Elliptic Curve Land, there lived two kangaroos on a mission to solve one of Bitcoin’s deepest mysteries: finding
k such that
k · G = P. To be fair, no one asked kangaroos to solve the discrete logarithm problem, but that’s where we ended up. Blame cryptographers. They just really love making things unnecessarily complex.
So, we had two types of kangaroos: one
Tame and one
Wild, both with vastly different ideas about how to go about the job.
The Tame Kangaroo: Mr. Organized (a bit too much)The
Tame Kangaroo was the sort of kangaroo that kept spreadsheets for everything. It approached the problem with the
Baby Step Giant Step (BSGS) method. Step one: methodically start from a known point and hop forward in
baby steps, taking small, calculated leaps along the elliptic curve. Every step was carefully recorded in what cryptographers would call a “hash table,” but really it was just a fancy scroll of distinguished points.
Each point was a “distinguished point,” which is cryptographer-speak for "the Tame Kangaroo decided this point was important, even if no one else cares." The kangaroo filled its scroll with these, convinced that someday, all this careful planning would pay off.
“Slow and steady,” the Tame Kangaroo mumbled, hopping one tiny step at a time. Of course, slow and steady also means
slow, like the kind of slow that makes you question if elliptic curves are really worth it. But the Tame Kangaroo was committed, carefully calculating every single move, knowing it was storing each of these baby steps for future reference.
Once the scroll was filled with baby steps, the Tame Kangaroo moved on to
giant steps. Now, instead of inching along like a cautious librarian, it started bounding across the elliptic curve with bigger leaps. Giant steps! Progress! But of course, every few hops, the Tame Kangaroo had to stop and check its giant scroll of baby steps, making sure it wasn’t missing anything. This was still BSGS, after all. Planning was everything.
The Wild Kangaroo: Leaping Without a PlanMeanwhile, the
Wild Kangaroo couldn’t have cared less about precomputation. Baby steps? Scrolls? Giant steps? Nah, it had a different strategy:
random hopping. Armed with nothing but a vague sense of direction and the
Kangaroo Method, it launched itself into the curve, jumping around at random like it was trying to escape the logic of elliptic curves altogether. The Wild Kangaroo didn’t precompute anything. Why would it? If it hopped enough, surely it’d land on something important.
Now, this hopping wasn’t completely without structure. The Wild Kangaroo relied on those
distinguished points—because even chaos needs occasional markers to know it’s not completely lost. Every time the Wild Kangaroo landed on one of these distinguished points, it would stop and look around, hoping the Tame Kangaroo was nearby.
“Who needs a plan when you can just bounce around until something works?” thought the Wild Kangaroo, probably mid-leap. And, honestly, it wasn’t wrong. The Wild Kangaroo’s approach was all about finding
k through sheer trial and error, covering large parts of the curve quickly, and hoping the Tame Kangaroo would eventually cross paths with it.
The Moment of CollisionBoth kangaroos were now bounding around the elliptic curve, one methodical, one chaotic. The Tame Kangaroo carefully hopping in giant steps, pausing to check its scroll every few leaps, and the Wild Kangaroo bouncing between distinguished points, blissfully ignoring the concept of “memory.”
And then it happened.
They collided.
Right on the same distinguished point, both kangaroos landed at the exact same time. For a brief moment, they just stared at each other, both surprised that they had ended up in the same place.
“I spent days calculating every hop,” the Tame Kangaroo muttered, exhausted from all the memory management. “Giant steps, baby steps, a whole scroll of computations.”
“Oh,” said the Wild Kangaroo, scratching its head. “I just kinda… jumped around and got lucky.”
The Tame Kangaroo sighed. After all that work, the Wild Kangaroo had stumbled onto the same solution without bothering with any of the precomputation, baby steps, or giant scrolls. They both had the value of
k, but only one of them had bothered to keep notes.
The Final Lesson: Kangaroo Chaos Works, Sort ofSo, in the end, they both cracked the elliptic curve problem. But here’s the thing: the
BSGS(Kangaroo) method works, sure, but the
Kangaroo Method doesn’t care about your fancy scrolls or precomputed baby steps. It hops randomly from distinguished point to distinguished point, hoping to get lucky—and sometimes, it does.
The moral of the story? You can spend ages carefully calculating every baby step, or you can jump around without a plan. Both approaches will get you to
k, but the Tame Kangaroo will be left wondering if all that meticulous planning was really worth it when the Wild Kangaroo got there by sheer dumb luck. In the world of elliptic curves, sometimes random hopping works just as well as careful thought—especially when the math is more stubborn than a kangaroo in mid-leap.
