The goal is ~512GiB worth of precomputed points (@ 16bytes/point).
I remember that the DPs are not equally useful:
https://eprint.iacr.org/2012/458.pdfFor the range [a,b] if we have pre-calculated (b-a)^(1/3) distinguished points, we would need only (b-a)^(1/3) group operations in order to find the collision. But precomputation requires (b-a)^(2/3) group operations (performed once as a preliminary stage).
EDIT:
source (see 2nd paragraph on page 6):
https://eprint.iacr.org/2014/565.pdfIf we split 2^110 in 2^20 ranges each of length 2^90, for each range it would take only 2^30 steps to retrieve (on average) the key. In theory 2^20 * 2^30 = 2^50 steps would be enough.
Even if we look in different ranges, we can share the same 2^30 DP points. Each interval can be shifted in the range [0, 2^90] together with the public key P.
It becomes very important to generate this 2^30 DP points (but it requires 2^60 steps).
If we split 2^110 in 2^29 ranges each of length 2^81, for each range it would take only 2^27 steps to retrieve (on average) the key. In theory 2^29 * 2^27 = 2^56 steps would be enough.
And we would need to generate first 2^27 DP points (it requires 2^54 steps).
About using an experience of previous work.
---
The result is that experience helps you find the key in the current range or in the previous one, but it is absolutely useless to search in the following range that is multiple large to the current one.[/b]
In other words, in order to solve the puzzle faster you need to move from end to beginning .. first 125, then 120, then 115 and then 110))
There is a small exception:
if you have found DPs in the interval [0, 2^109], then you have found actually DPs in the interval [-2^109, 2^109], therefor you have already the DPs for a double range.
