BSGS VS Pollard Rho

[JackMazzoni]

BSGS VS Pollard Rho

If use 1 RTX 4090 Using BSGS and another 1 RTX 4090 using Pollard Rho .
Which is faster and what are their speeds per second?

I want to know based on real experience no AI please.

Is there a vram bandwith bottleneck slowing down the BSGS? is this true?

[flapduck]

If you're talking about secp256k1 against a normal random key, the honest answer is neither wins in any meaningful way. Both are still living in the same sqrt(N) universe, and for a full 256-bit keyspace that's basically "heat death of the universe" territory.

So the only time this comparison matters is when you've already got a constrained problem, like a known interval, partial bits, a broken RNG era keygen, or some other structure that collapses the search space.

[kTimesG]

BSGS is memory-bounded and requires storing and/or looking up each computed point.

GPUs are not built for solving memory-bound problems, they are compute-oriented devices. They can compute points very, very fast, but if each of those points (living in GPU registers - basically on the transistors directly connected to the execution cores) need to pass through to VRAM, it's pretty much game over (expect a slowdown by 100x and plenty of other bottlenecks).

So, Pollard Rho wins here, since memory access is basically zero. However, Rho is only useful if the interval is not known (e.g. the key can be anywhere in the full scalar domain, not restricted to a range).

Also there's not enough total memory on planet Earth to be able to run a real BSGS solver, using any device in existence (GPU, CPU, or clusters of supercomputers), if the interval size is above 100-ish bits. And even so, all of that memory would have to be connected to a single central computer, otherwise it's no longer fast memory, it's a disk storage database,. Such technology does not yet exist, and it's pretty much an alien-technology level fantasy.

[JackMazzoni]

I'm interested in real data using 4090 based on your experience. FYI this only for puzzle where the range is known.