Quote from: kTimesG on February 22, 2025, 11:06:31 AM

Quote from: hoanghuy2912 on February 22, 2025, 04:36:39 AM

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¹³⁴

BSGS requirements:

1. Fast memory baby table: sqrt(N) items = 2⁶⁷ 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 bits = somewhere between 2⁷³ to 2⁷⁴ bits

The total amount of data stored on Earth in 2018 was 33 zettabytes. That is, 2⁷⁸ 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⁸⁰ 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⁶⁸ 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⁶⁸ / 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)

Mathematics is like sex... if you go too fast, you miss the best part. Grin