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
134BSGS requirements:
1. Fast memory baby table: sqrt(N) items = 2
67 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: 2
67 * 67 bits = somewhere between 2
73 to 2
74 bits
The total amount of data stored on Earth in 2018 was 33 zettabytes. That is, 2
78 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 2
80 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 ratio 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, 2
68 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 to solve in one second: 2
68 20.000.000 = 14,757,395,258,968
In summary:
RAM: 1 to 2 zettabytes
CPU threads: 14.8 trillion (for 1 second of total work)