The goal is ~512GiB worth of precomputed points (@ 16bytes/point).
I remember that the DP are not equally useful:
https://eprint.iacr.org/2012/458.pdfChoosing the most useful distinguished points.
Instead of randomly generating T distinguished points, we propose generating more distinguished points,
say 2T or 10T or 1000T, and then keeping the T most useful distinguished points.
(This presumably means storing 2T or 10T or 1000T points during the precomputation, but we follow standard practice in distinguishing between the space consumed during the precomputation and the space required for the output of the precomputation. As an illustrative example in support of this practice, consider the precomputed rainbow tables distributed by the A5/1 Cracking Project [26]; the cost of local RAM used temporarily by those computations is much less important than the network cost of distributing these tables to users and the long-term cost of storing these tables.)
The natural definition of “most useful” is “having the largest number of ancestors”. By definition the ancestors of a distinguished point are the group elements that walk to this point; the chance of a uniform random group element walking to this point is exactly the number of ancestors divided by `.
Unfortunately, without taking the time to survey all ` group elements, one does not know the number of ancestors of a distinguished point. Fortunately, one has a statistical estimate of this number: a distinguished point found by many walks is very likely to be more useful than a distinguished point found
by fewer walks. This estimate is unreliable for a distinguished point found by very few walks, especially for distinguished points found by just one walk; we thus propose using the walk length as a secondary estimate.
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 DP in the interval [0, 2^109], then you have found actually DP in the interval [-2^109, 2^109], you have then already the DP for a double range.