Mark1 implementation of Pollard rho algorithm (38 minutes for 80 bits on CPU)

Hey everyone! Check out my version of the Pollard-rho algorithm: https://github.com/Dookoo2/Mark1 It takes about 38 minutes to crack an 80-bit puzzle using half a billion data points, and around 14 minutes for a 70-bit one with 200 million data points (after phase 1 where I gather and save the data points). I included an AVX2 bloom filter, a compact data point table, Brent's cycle detection, plus a few other neat features. Hope this helps someone out. Have a great day!

Great! Hope to get more speed

The code is good, but it’s missing the part where the script loads the saved DP.bin with the --load-dp option. Mark1.cpp Makefile Added new command-line option --load-dp <filename> to specify a DP.bin file to load Modified the Phase-1 section to either: Load from file if --load-dp is specified or generate new traps as before if not Added proper handling of the DP target when loading from file. Maintained all original functionality including: Saving DP with -s/--save-dp . All performance optimizations. All existing command-line options... How to Use: Generate new DP and save it: Load saved DP and continue searching: Generate new DP without saving (original behavior): P.S. I don't have Github. Someone can fork and upload this for me. If they want to...

Holy s*it. How fast is the file saved as DP.bin and loaded afterwards. Puzzle 70 solved in 10 seconds on my trash machine.

NoMachine, plz return your GitHub back! I like your coding skills (and readme files), and Mark1 is the deep refactoring and a few reingeneering of your Kangaroo-hops file. I updated Mark1.cpp code

Maybe this is a stupid question, but is it possible to make the same Kangaroo have both odd and even DPs, like @AlexanderCurl does? Could we reach 90-bit *f* this way?

That's only useful for brute-forcing, however brute-forcing is un-needed for DLP problems. For BSGS this trick is also useless because it requires shifting the key by range/2 (to have the same-X mapping to 2 points), but the shift itself may move the point in the left side, which means the solution will never be found (unless you use two giant points instead of one, so zero benefit overall).

Cool. But I did implement it, that's why I said it doesn't work. Otherwise, you might have explained things in a way that wasn't understood. It's pointless to use the X coord and use batch block points the way you (tried to) explain. It simply doesn't work the way you attempted to explain. And for kangaroo, this is even more pointless.

Thx for the template, but I already use that in my PointsBuilder demo. I think you misunderstood my point though. This batch addition that computes both P + Q and P - Q has no usefulness outside BSGS or simply building that specific array of results (e.g. for brute-forcing the H160). It simply slows down the processing, since there is nothing useful for having both of those points computed. Maybe you should read again what Akito was asking, but more carefully. The answer to his question is that having a DP obtained via P - Q will almost never be hit from another route then the current one, since the pseudo-random walk ends (the point is not used as a new base point). It's basically equivalent to  having a DP which is 1 bit lower, however the processing is slowed down. The probability of having it hit by another walk is so close to zero, that it's simply not worth computing it at all. RC does use it though, but not always, and it's for a different purpose anyway. And for rho or Kangaroo, you always, always need the Y coordinate, because it's needed to actually do the next jump. So your "let's only compute X" is useless for this case.

Eagerly waiting for someone to implement it just so they get bit in the ass. Maybe you should be the magician to do it, since you're the one claiming that it speeds up anything, using a concept that can only increase the number of operations (or even worse, that isn't even applicable to the issue). If something doesn't work on a freaking PAPER, I'm not sure how it could ever work in practice.

I've sent you back all the merit points I had. I now owe you the rest of 11 points, I will compensate it back when I can afford it. I don't need anything from people like you. Also, your idea is genius, so forgive me. That would be a cool Kangaroo Hopping!!! And your BSGS optimization is spot on. Let's reduce that bitch down to .5 sqrt, magical batch addition, yay.

Batch addition for static delta points and/or shared inverses to do P±Q doesn't work in Kangaroo nor rho (which is what this thread is about before you hijacked it with your evolutionary breakthrough). This was the whole point. Otherwise, you're simply trying to do something which has long been done in KeyHunt, JLP, etc. However it feels like you are stating that you found a way that saves on storage or lookup. Maybe you should take a piece of paper, draw your idea on it, and maybe notice how it fails reducing any of the complexity or required storage whatsoever. The intersection / collision can only be optimal if sqrt(n) points are stored, no matter what clever trick geniuses try to come up with. Here's what I got from you explanation. If it's wrong, maybe explain it better. You wanted to save / check the "middle points" or something like that, right? The red point is the real (and unique) BSGS collision, blue points are the saved points, green points are the checked giant points. Collision is missed since it would jump right through unsaved / unchecked points in both baby and giant ranges.

rubbish waste of time

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?.

Where did you ever read that the Kangaroo algorithm requires storing the DPs in RAM? Storing and querying DPs works just fine with a database. This allows collecting terabytes or more of DP data.

I'm referring to the dp.bin of this thread

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.

I have done it already:) switch Dp_table from RAM to SSD:) Bloom - RAM Dp_table - SSD Next step - I will add gpu computing secp256 with all logic from original version

Anyone already forked to have it in Visual Studio for Windows ?