Lenstra–Lenstra–Lovász lattice basis reduction algorithm is not a something that can be understood using simple mathematics.

Try to read this for example.

Hi, Alberto.

xpoint mode does not work at full possible speed, because FLAGSEARCH has default value of 2 (SEARCH_BOTH); then at thread_process you have following condition:
If you add an exception there for xpoint, unnecessary calculations of Y-coordinate will not occur and this will at least 1.5x speed in xpoint mode I think.

You can't because GPU uses only 128 bit variable to store distance on each kernel call, it means that when kangaroo jumps out of 128 bit space, all subsequent jumps are calculated incorrectly.

130 puzzle still can be solved with unmodified JLP's kangaroo if you divide 129 bit space into two 128 bits parts, but kangaroos still can jumps out, so you have to control the wrong DPs.

I don't see any benefits of this. If you have N baby steps with 1 bit of each, then roughly N/2 steps will collide with each giant step. This mean you will need to perform at least N/2 additional operations on each giant step to check false positives.

This leads to the fact that the ability to store n-times more baby steps leads to an n-times increase in the size of the giant step, but at the same time increases the number of operations required to check the collision by the same number.

Simply put, this ultimately will not give any increase in speed compared to maintaining the full baby step value.

It's just because both generators were created by doubling the same point.

Jump table generator uses hard-coded fixed seed each time to keep jump sizes equal for all workers.

I don’t know what else to answer you other than what I already wrote.

Anyway, as I wrote above, if anyone else besides me is still interested in finding out the key to 120 and still has kangaroo's workfiles for 120 puzzle with DP of 30 bits and above, please share them. Workfiles for 125 not interesting me, because I did not work on it.

I already wrote the real reason. Or are you expecting me to write something like "using the 120 key, I know how to calculate 130"? Unfortunately, this is not so, and if it were possible, then the one who found 120 and 125 would have solved the next puzzles long ago.

I strongly doubt that this will somehow help to solve 130 or 66, just as the keys 63, 115 and below previously did not help to solve 120 and 64. This is just something like scientific interest. I previously spent a lot of time and resources trying to solve puzzle 120 and I'm still curious about its key. If the finder or puzzle's author would just publish the key itself, I would also be grateful.

Even though the 120 key was found, I'm still interested in finding it since it hasn't been published. If anyone still has kangaroo's workfiles for 120 puzzle with DP of 30 bits and above, I would be grateful if you share them.

Because statistics are wrong until all threads loads kangaroos. Wait about 10-15 seconds to get right numbers.

With a high level of entropy that sha256+rmd160 provides, I would say that from a mathematical point of view, the desired address is quite far from addresses starting with similar letters. Therefore, in theory, we can exclude some ranges from search where addresses with similar prefixes was found. But anyway the real random is the kind of thing from which you can expect anything.

Everything is much simpler than it seems if you forget about decimal fractions and work with it as with simple fractions.

4501/230 = 19 ¹³¹/₂₃₀ Fraction part = 131/230 or 131*modinv(230) on curve

4500/230 = 19 ¹³⁰/₂₃₀ = 19 ¹³/₂₃

⁴⁵⁰¹/₂₃₀ - ⁴⁵⁰⁰/₂₃₀ = ¹/₂₃₀ => difference on curve = 1*modinv(230)

If you really need to find decimal fraction, just convert it to simple fraction:
0.5 = 5/10 = 1/2 = 1 * modinv(2) (or 5*modinv(10) - doesn't matter).
0.434783 = 434783/1000000 = 434783*modinv(1000000)

I tried and tested similar approach a year ago. The best result I could achieve is O(N/4) complexity for a random number, but only if this number is composite. This is 4x better than bruteforce, but it's requires a lot of scalar multiplications, therefore optimized sequential key generation is still faster despite the higher complexity of O(N).

When the solver move reward from 64 puzzle, it public key has been revealed; after that, finding a key in such a small range is trivial.

Do not fix on EC points, elliptic curve is just "graphical" interpretation of a numbers, all maths behind it works at finite field and obey all laws of "real" numbers math.
If you divide any "real" number by 35, then divide number+1 by 35, then difference between results will be 1/35. This is also works in finite fields and for EC points.



This is not true, for example - 26/5 = 5,2; 35/5 = 7; 9/5 = 1,8. 26/5+9/5 = 5,2+1,8 = 7 = 35/5
you can also check this with EC points like:

output:

Kangaroo can find a key in any range, regardless of its size. Even if you specify the wrong range, kangaroo will still find the key, but it will take much longer.

JLP's kangaroo implementation does have a problem with small ranges because by default there are too many kangaroos in a small range. You can adjust CPU/GPU group size to fix it, search with cpu only, or search with less threads/grid size.

Regarding searching for multiple keys, the kangaroo algorithm only works with one key at a time, so such a search is only possible sequentially. If it were possible to search for several keys simultaneously without loss of speed, then the puzzle's addresses with revealed public keys would have been solved long ago.

If you're using division by a fixed number, first you can cache inverse of this number to avoid inversion on each step, second you can decompose inverse into fixed double-add chain, then optimize it with special formulas for point tripling and readditions. But it is will be still expensive opertaion.

This is what is called a Baby-step-Giant-step (BSGS) algorithm. There is many good and optimized implementations of this algorithm, including GPU implementations.
If you generate sequence of 10 successive keys, you can check every 10th key in range to hit some key in sequence, 100 keys - every 100th and so on.
But to achieve this you don't need to change G at all.

Then explain the difference please.

I looked at the piece of code you wrote above, looks like it works like BSGS algorithm, with a very naive implementation.
The first thing that you should do, it is remove curve multiplication at all and replace it with subtraction.
I'm talking about this part: PublicKey = getPublicKey(Seq_Bytes)
Every call of "getPublicKey" is very expensive, no matter which point you're uses as "G".
Just take another point (G*100) as a stride and subtract it from current point on each step. Than you will get 6000, 5900, 5800, 5700 and so on with a great speed improvement. Trying to do the same by replacing the generator point is pretty bad practice, despite the fact that from some side it will certainly work.