Quote from: WanderingPhilospher on Today at 12:57:12 AM

Quote from: kTimesG on August 28, 2024, 03:11:38 PM

Quote from: nomachine on August 28, 2024, 12:32:04 PM

Puzzle 130: ~ [Expected Hops: 2^65.64 (57392798431464251392)]

How much storage is needed to precompute Puzzle 130 ?

1. That number is kind of a reference point, can vary ± 20% Besides, the best known complexity is rather 1.66 * sqrt(b) but requires special attention when jumping through the point at infinity. Speed is better when we're certain we'll never need to double a point or go through O, since that special branch goes away..

2. It's non-sense to precompute stuff when you know all the variables. It's just faster to solve the problem. Pre-computation makes sense to search and save traps inside the same space where the wild kangaroos will jump around.

You don't need any storage to solve 130 or 160 or 66 or 250+ bits. Storage is only needed if DP > 0 or if you have more than a single Tame and Wild kangaroo. But since we don't have forever to do all those gazillion ops, the catch is to compute a lot of kangaroos in parallel - as we definitely can't compute just two kangaroos in parallel, the next jump depends on their current value.

So storage depends on whatever you wish to accomplish. Might as well just save an ID of the kangaroo that reached a DP, and re-create the walk when a match occurs, to get the distance. But it's slow if the walk was a long one.

Agreed, no need to pre-compute a huge range like 130, unless you are going to run through it multiple times looking for different pub keys, but not really even then because you can tame every wild kangaroo that ran through the range, after the key is found.

Pre-compute is just running all "tames"... (k*g) through whatever range and store the points (public key x points, not the whole thing but however many bits you chose (not to few though or then you have false collisions)) That's all pre-computing really is. Same as BSGS, 1*g all the way up to however many points you want in your baby step file. And all of those points are DP 0.

For the 130 puzzle, we are using DP 32. So we will roughly need to find 2^33.55 distinguished points. File size, should be right around 400GB; that's my estimate.

And albert0, since you know BSGS better than most, a 100,000 view way to look at Kangaroo, consider the baby step file the tame kangaroos, and the giant steps, the wilds (offsets). BSGS is like a brute force mixed with Kangaroo lol. But Kangaroo is just more spread out with it's jumps, whereas BSGS takes the exact same "step" each time. Kangaroo creates multiple offset pubkeys (addition or subtraction or both), those are the wilds. And once one of those offset points matches a tame point, basic math just like BSGS.

Tames are just k*g, with some distinguishable point. The 130 pool, DP 32, so we save every x point that has at least 8 zeros at the end (trailing). The wilds are k*g + public key, that you are searching for. Same thing, if it ends with 8 zeros, it gets stored. Once we get a collision / match, we merely take the tame distance (k*g or private key really) and subtract the wild distance. And like BSGS, if you reduced the range by subtracting the start range up front, then you have to add it back. (tame distance - wild distance) + initial subtracted start range.

Very nice and clear explanation about the kangaroo and BSGS methods. Cheers WanderingPhilospher!