Quote from: RetiredCoder on February 26, 2025, 09:16:11 PM

Quote from: Veliquant on February 26, 2025, 05:31:22 PM

I have been studying the puzzles for a year now. I was able to comunicate with professor Teske and professor Galbraith, they both worked with professor Pollard, and pointed me in the right direction. I have some questions and some original ideas about the pollard methods.

Quote from: Veliquant on February 26, 2025, 08:18:30 PM

I understand that you use a base magnitude for the jumps and add a random portion to make the jumps, in a different way for each of the 3 heards, I will study this in detail.

It seems you don't know how it works even after a year. The jump table is the same for all herds, otherwise it won't work.

Quote from: Veliquant on February 26, 2025, 08:18:30 PM

I'm not able to find an implementation for batch inversion on your code, do you use batch inversion to speed up the computation of the inverses? I understand that in the Classic Pollard method, you can use this approach, computing the next point for a group kangaroo paths. This will make the cost for one inversion only 3 - 4 multiplications? Is that correct?

For CPU code I don't use batch inversion because I tried to make the code as simple as possible. That code demonstrates various methods for ECDLP and loop handling, not optimizations.
For RCKangaroo I use batch inversion, check its CUDA sources.

Yes you are absolutely right, after one year of dreaming with babies, gigants and kangaroos, I understand that the jump table has to be the same for all herds Grin

.

For me is very interesting the way you see the kangaroo methods conceptually. There is one part that is the method itself were we try to make as little as possible point additions, the other part is "optimizations" were we try to make those point additions as fast as possible, and use parallel computing to increase the point output.

I understand why is so important the concept of "K", I have an intuition about this that i would like to ask if it is correct. The kangaroo method by itself as in only 2 kangaroos (Tame and Wild) would solve the discrete logarithm in only sqrt(range) steps (k = 1) if both kangaroos started at the same point. This is sqrt(range)/2 for each kangaroo. This is related with the birthday paradox. Wen you use the first method in your program, and the kangaroos are separated, there is an overhead, because the path before both kangaroos meet is wasted. This accounts for an additional K points, so this method will solve in 2K jumps on average. What I have not been able to understand is how the 3 kangaroo method works. You start with one tamed an 2 wilds, and place them in a different position. This makes the kangaroos meet faster on average.

There is also the concept that if you start the path in the origin, and jump to the right, is the same as jumping to the left, so you are actually making, 2 paths at once.

For the 3 kangaroo methods this are my questions:

1) Where the 3 kangaroos should be placed at the beginning?
2) The wild kangaroos travel 1/4 of the jumps each and the tamed 1/2 of the jumps?

Thanks

Veliquant

Posts

Merits