BSGS Algorithm Implementation for Nvidia GPUs

Just put together my version of the BigStepGiantStep algorithm for Nvidia cards. Works on Cuda and Windows x64. Check it out here and share your speed results.

Looks like you're familiar with BSGS and x86 assembler... I modified Jean's BSGS for curve 'r1' while btc uses k1. What’s the deal with the start value? Does the searched k need to be in that range?

Sweet, I’ll update you on speeds across different GPUs once I run some tests.

For sure. Your project seems way more user-friendly than that JLP kangaroo thing. Tuning that one is such a hassle!

Just tried out your BSGS on my GTX 1660s and it was slower than JeanLucPons' Kangaroo. BSGS-cuda hit 330 Mkey/s, while Kangaroo got 450 Mkey/s.

We really need to see how long it takes to find a sample private key. What’s the fastest code for this?

COBRAS, how about you jump in and start testing? Or are you waiting for someone else to do it?

With v1.2 on a single 2080ti, I solved some pubkeys in about 28 minutes with params -w 26. Compared to JLP's CPU version, that’s six times faster!

Nice! But how quick would it run with the full range from zeros to f's?

How much memory do we need for each babystep? Is the hashtable using GPU memory or global RAM?

Lol, definitely some sarcasm there. COBRAS doesn’t seem to contribute much. His last comment made no sense at all.

Had my RTX 3070 running at 1,000 MKey/s with default settings. Didn’t mess with anything to optimize.

I ran the same benchmarks as Etar and JLP for 16 pubkeys. JLP on CPU took 3 hours and 35 minutes for comparison.

Each baby step uses 8 bytes. The hashtable is stored in the GPU memory. With -w 26 and -htsz 25, it generates quite a bit of babysteps.

Thanks, Etar! I think your BSGS-cuda outperforms JLP's version. JLP is solid but takes way too long on my GPU.

Mandatory update v1.2.1 is out now. Fixed some bugs with multi-GPU searching.

JLP's BSGS is CPU only, while yours supports GPU. Side by side tests show that BSGS Cuda is faster for multiple pubkeys.

You’re right. Sorry for the confusion. I just meant it was slow on my laptop, so slow that I sometimes just quit waiting.

Works well in the 65-bit range, but hitting 120-bit seems limited. Still can’t get a key in the 65-bit range.

Searching these two pubkeys in the 100-bit range, anyone got hardware info for this? What GPU models are you using for those results?