To be able to use keyhunt's bsgs mode to scan and solve puzzle 135 as fast as possible, how many CPU threads and RAM are needed at the same time? How long does it take to scan the range 4000000000000000000000000000000000:4ffffffffffffffffffffffffffffffffffff?
Puzzle 135 range size: 2
134[/b]
BSGS requirements:
1. Fast memory baby table: sqrt(N) items = 267 items
Item size: 256 bits in full; let's assume we only need the first 67 bits and ignore hash collision overhead
Total memory required: 267 * 67 bits = somewhere between 273 to 274 bits
The total amount of data stored on Earth in 2018 was 33 zettabytes. That is, 278 bits.
Estimates for 2025 are around 175 zettabytes. That s, all of the hard drives that exist on Earth have some total capacity of around 280 bits.
The amount of RAM is less than a fraction of all that (if you don't believe this, check any PC: what's the ration between RAM and storage capacity?)
2. How many threads?
EC operations required at most: sqrt(N) for baby steps + sqrt(N) for giant steps = 2 * sqrt(N) steps
That is, 268 elliptic curve group operations.
A high-end CPU can do around 15 to 20 Mo/s per thread. However, we also need to check the table after every giant step. I will ignore this and assume it is a no-op (it's not).
Total threads needed: 268 / 20.000.000 = 14,757,395,258,968
In summary:
RAM: 1 to 2 zettabytes
CPU threads: 14.8 trillion