How many pieces of DIN A4 paper are needed to find #135?
Now we're talking! Great question!
Let's organize the setup:
A4 sheets: 0.1mm x 21mm x 29.7mm
Average height of human calligraphy: 14pt (around 28 rows / sheet)
Estimated group operations on secp256k1: 2**66 optimistically, 2**68 pessimistically (warning: this may go lower or higher)
Each group operation, given that we'll use all sorts of optimization tricks (batched inversion, shared inverse, pseudo-Mersenne reductions during MUL and SQR), is composed, let's say, of:
1 INV (inversion) for, let's say, each n = 1000 points (go as high as you can, but logistically it may become a problem: are there enough A4 papers at disposal, per batch?)
3 * (n - 1) MUL (256-bit multiplications, and reduction, mod p) for the Montgomerry trick (batched inversion prefix and postfix products)
2 * n MUL for computing each slope, for P + Q and P - Q
2 * n SQR + 4 * ADD needed to compute each x3
2 * n MUL + 4 * ADD for each y3
Note: we can use some temp for the shared (- x1 - x2) so YMMV here.
Now, let's add up the required resources.
1 inversion: probably bingcd / safegcd / EEA XGCD would take some good 200 sheets of A4. I think gmaxwell brought it down to around ~ 500 half divisions. You need to know your matrix calculus pretty well though. Otherwise, keep it simple and use Fermat's Little Theorem, but you'll probably need lots more paper.
1 MUL: maybe 10 sheets (but likely with very very small hand writing, you do end up with physical limitations when multiplying some 80-ish digit numbers!
If you want to be cool, do the reduction while multiplying. If you know your shit even better, use Karatsuba, or even the FFT O(log log log n) multiplication, to save on space.
1 SQR: slighly less, maybe 8 sheets. Yeah, some digit pairs show up twice, so you finish faster!
1 Addition / subtraction: 1 sheet per each.
Now, you may notice that this all varies by the number of points (e.g. number of walks you are prepared to compute at once).
It's stupid to simply do a single walk (though it works just fine) since you lose the batch inversion benefits). Let's not be dumb, we're likely better off with around 100 million walks, for such a great adventure like Puzzle #135.
So, for n = 100 million:
Optimistic scenario: 2**66 ops
Batched steps: 2**66 / 100.000.000
That's 148 trillion A4 sheets just for all the INV for all the walks.
Prefix/postfix MULs: 2 * 10 * 2.21 * 10**20 sheets.
For slopes: 10 * 1.47 * 10**20 sheets
For x3: 8 * 1.47 * 10**20 sheets
For y3: 10 * 1.47 * 10**20 sheets
I haven't included the sheets needed for the ADD ops, I mean you can use some corners or something, they're pretty cheap.
FINAL BREAKDOWN (computation part only, optimistic scenario):
The total height of your A4 sheets would come down around to 8.536×10**14km
That is around 5.7 million AU (astronomical units), or 90 light years.
Total weight: 4.268×10**19 kg (around 0.00072% of the Earth's mass)
That is around 10.000 times the mass of all humanly built things over the course of history.
Now, you'll also need a DP database so you know when to end this thing. However, you'll need some hooks at this point, together with post-it notes, since the lookup tree needs to be dynamically balanced as you add DPs to it. If you also want to know "how many hooks and post-it notes do I need to solve 135" please LMK. Glad to help.
