Re: Mark1 - pollard rho implementation (38 minutes for 80 bits solving on CPU)
I think the next point to address regarding the Kangaroo algorithm is to avoid loading the DP into RAM. I think that is a strong limiting point for Kangaroo, especially when it comes to high ranges.
Has anyone thought of any interesting ideas to solve this?.
Has anyone thought of any interesting ideas to solve this?.
It ain’t worth makin’, but you could totally build a Memory-Mapped DP Table System that mixes a Bloom filter (in RAM) with a memory-mapped DP table (on disk). Gotta reserve, like, 2-3x the expected DP table size to keep things runnin’ smooth. And for those massive tables over 1TB? Yeah, you’ll need to split ’em across multiple files.Just like I did in my BSGS. But here’s the catch: If someone’s crazy enough to try solvin’ Puzzle 135, they’re gonna need thousands upon thousands of terabytes of storage.
I was once thinking about including my lightweight database in Kangaroo, but I never finished it; I lost interest.
But the two ideas that came to me back then were to create a file where the DP would be stored, sorted like any other database. For active searches, I would only store the parity (like the first lightweight databases). Instead of using the 64-point continuous parity, I used the DP parity. So, when the kangaroos collided, they had the same sequence of DP from that point.
Basically, I had a breadcrumb trail of their paths. Once the collision height was calculated, I would identify it in the file's database and retrieve the complete information to construct the private key.
and the other idea was the same with the bits but using deterministic seeds that were stored in a file, when the collision of the bits was detected the path was reconstructed with the seed used, but I didn't think about this much since if you had made many jumps, reconstructing the path could take too long, unless a different seed was used every certain number of jumps, or some type of checkpoint was used to speed up the reconstruction.