origin link

https://fe57.org/forum/thread.php?board=4&thema=1#1..Let's discuss the Pollard's kangaroo script from 57fe since it is not possible to register on its forum. Has anyone managed to increase the speed above 150k?..

Let's!

I will conduct a lot of tests and update this post.

Last update at Sep 15 2019, edit#29

#################

Notice, about power, it is the same

2

^{123} == 2^(123) == 2**(123) == pow(2,123) == pow2(123) == 1<<123

sqrt(2) == 2

^{1/2} == 2**0.5

2

^{123} - only this forum, outside of quote/code tags

2** - its python specific

pow() - popularity in many programm langs

2^ - classic old standart math text format, so i use it in 99%, not beautiful but it works

here x^y is math text format of power as x

^{y} and not bit operation xor as [x xor y], do not confuse!

#################

# gmpy2

When I ported the code to coincurve lib, I was surprised to find that gmpy2 is faster.

Until this moment, I have not seen an implementation faster than in coincurve, my respect!

1core i5-2540 python37x64 win7x64

coincurve: 30528.2 j/s

cffi+coincurve: 41165.6 j/s

gmpy2: 90194.8 j/s

(with python27x64 -10%)

(on linux +20% and more!)

how to install gmpy2 on windows

1) download file .whl from

https://www.lfd.uci.edu/~gohlke/pythonlibs/ 2) put to root dir of python

3) install

Python27>python -m pip install gmpy2-2.0.8-cp27-cp27m-win_amd64.whl

Python37>python -m pip install gmpy2-2.0.8-cp37-cp37m-win_amd64.whl

#################

# speed cpu

..Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code..

..because this is the limit of computation on the cpu

take for example break_short

1core i5-2540 = 0,16 Mkeys/s (C secp256k1 x64 without calc Y) (A + J -> J; xJ -> xA)

add(points) using every loop in break_short

add(points) using every jump in kangaroo

therefore their speed is equivalent

#################

# about kangaroos algo by 57fe

..Now we give the improved algorithm of [11] (for a serial computer).

The two kangaroos now make alternate jumps, and T starts at the middle of the interval, i.e. x0 = r^{M} , where M = [(L + U)/2].

Whenever xi falls in D, we store the pair (xi, di) together with the name of the kangaroo (T or W).

This information may be stored in a hash table, hashing on xi.

When some xi is stored for the second time, having been reached by both kangaroos, we can compute the solution.

Thus, if xi(forT)=x'j(forW), we have z = M + di - d'j .

In this version, unlike [5], we do not know which kangaroo is in the lead,..

this is based of [5]

Launch m/2 tame kangaroos with starting points g^{(b/2)+iv}, for 0=i<m, where v is a small constant

(avoid a power of 2 for v so that the probability of tame kangaroos following the same path is not abnormally high).

At the same time, launch m/2 wild kangaroos with starting points yg^{b+iv}, for 0<=i<m.

Whenever a kangaroo lands on a distinguished point, store it in a list common to all processors.

With each distinguished point, store a flag indicating the kangaroo type (tame or wild) and the distance

from g0 (for tame kangaroos) or from y (for wild kangaroos).

Suppose that a kangaroo reaches a distinguished point that is already in the list.

If the kangaroos are of the same type, then move the trailing kangaroo forward by some small random distance so that it will not repeat the other kangaroo’s path.

If the distinguished point was produced by kangaroos of different type, then subtract the distances to get the desired logarithm and we are done.

and this is parallelism of [11]

[5] J. M. Pollard, Monte Carlo methods for index computation (mod p), Math. Comp., #32 (1978)

[11] P. C. van Oorschot and M. J. Wiener, Parallel collision search with cryptanalytic applications, J. Cryptology, #12 (1999)

I studied the source:

- used pre-calc Set jumps with size pow2 (by Pollard)

- creates 8 Tame kangaroos + 8 Wild kangaroos (idea 1T+1W by Oorschot&Wiener of [11]);

..but why 8/8?? 1/1 be must norm.. if set 1/1 - speed drops - calculation of jumpsize and startrange not optimal..

..i think, author try fix low efficiency (see below "anomaly detected"), or its trick to avg runtime, but fact - its slower -30%

(answer: variable kangoo_power (number kangaroos in herd) affects the step size, so the illusion is created that T8+W8 is optimal, although in fact it should not differ from T1+W1)

- gradually added new distinguished points in T+W sets that pass through DP_rarity (distinguished points for economy ram by Oorschot&Wiener);

hmm... has problem:

..where 0 <= uj,vj < r are chosen uniformly at random..

...

Launch m/2 tame kangaroos with starting points g^{(b/2)+iv}, for 0 <= i < m, where v is a small constant

(avoid a power of 2 for v so that the probability of tame kangaroos following the same path is not abnormally high).

...

We analyse a variation of their method, which avoids thepossibility of “collisions” between members of the same herd.

The numbers of kangaroos in the herds will be coprime integers u and v, nearly equal, with u+v=P.

Thus if P=4p, we could take u=2p+1 and v=2p-1. Their jumps will all be multiples of uv..

coprime integers! or 2p(+/-)1 integers! not equal random.randint(1,(1<<(problem-1))) !

and uniqueness new point is not checked.

some kangaroos can falls into the trap of same sequences (without new distinguished points);

..If the kangaroos are of the same type, then move the trailing kangaroo forward by some small random distance so that it will not repeat the other kangaroo’s path..

this reduces speed, jumps indicating norm, but really there are many calculation useless same sequences.

..If there is a collision between two kangaroos of the same herd then it will eventually be detected when the second one lands on the same distinguished point as the first.

In [473] it is suggested that in this case the server should instruct the second kangaroo to take a jump of random length so that it no longer follows the path of the front kangaroo.

Note that Teske [606] has shown that the expected number of collisions within the same herd is 2, so this issue can probably be ignored in practice.

omg, but ok

#################

# Most famous optimizations of Pollard

# about complexity, runtime and RAM

1) not use distinguished points (early, of [5])

..runtime of approximately 3.28w^{1/2} group operations

minimal RAM

2) use distinguished points

..The kangaroo method (of [11, p. 13]) can solve in about 2w^{1/2} expected operations..

It is expected to take 1.64 times faster than early, of [5].

need more RAM for saved points

why use distinguished points more efficiency

..by keeping previous data, the number of collisions found grows as the square of the time spent..

(because, the number of pairs of points grows as the square of the number of points produced)

"three-kangaroo algorithm"

("Using Inversion", but I think it means symmetry of Y)

One can perform a version of the kangaroo method with three kangaroos:

One tame kangaroo starting from g^u for an appropriate value of u and two wild kangaroos starting from h and h^(-1) respectively.

runtime (average-case expected) of 1.897w

^{1/2} group operations if m=0.316w

^{1/2} (m is avg size 1 jump)

runtime (average-case expected) of 1.818w

^{1/2} group operations if m=0.375w

^{1/2} "four-kangaroo algorithm"

runtime (average-case expected) of 1.714w

^{1/2} group operations if m=0.375(2w

^{1/2})

other algo avg runtime for compare

"Gaudry-Schost algorithm"

The basic idea of the Gaudry-Schost algorithm is as follows. One has pseudorandom walks in two (or more) subsets of the group such that a collision between walks of different types leads to a solution to the discrete logarithm problem.

runtime (average-case expected) of 1.660w

^{1/2} group operations

"Baby-step Giant-step” method of Shanks

runtime (average-case expected) of (3/2)w

^{1/2} group operations if first compute Baby and save in hashtable

runtime (average-case expected) of (4/3)w

^{1/2} group operations if compute both sets at the same time (double RAM)

very more RAM, w

^{1/2}pollard-rho

Theorem1 - 1.25w

^{1/2}..Theorem1 makes the assumption of true randomness.

However, it has been shown empirically that this assumption does not hold exactly for Pollard’s iteration function.

The actual performance is worse than the expected value given in Teske..

In prime order subgroups.. is 1.55w

^{1/2} and Teske is 1.27w

^{1/2}..while in groups of points of elliptic curves over finite fields.. is 1.60w

^{1/2} and 1.29w

^{1/2}1) Floyd improvement, y value is updated at each step y=F(F(y))

gcd is calculated for N and (y-x)

Floyd’s method needs on average 2.47(lt + lh) group operations (2.47 is three times the expected value of the epact).

2) Brent improvement (Brent improves Floyd)

check only (xi, xj), where j=2^k; k=1,2,3..a; i=[2^k+1; 2^(k+1)]

Brent has given an improved cycle finding method that still only requires storage for two group elements but which requires fewer group operations.

Brent’s method is 30-40% faster than Floyd’s. minimal RAM.

3) Teske improvement, used 20 kangaroo instead of 3(rho), +20%.

..running time the assumption is made that a random walk in the underlying group is simulated.

..this assumption does not hold for the walk originally suggested by Pollard: its performance is worse than in the random case.

..introduce a class of walks that lead to the same performance as expected in the random case.

Thus the complexity of Pollard rho method is determined by the size of the base group G on which random walk is performed and the running time of the iterating function.

Reducing either one of these two factors will result in speedup of the Pollard rho

...

In fact, the result on generic algorithm complexity implies that, to achieve results better than normal Pollard rho, we should either exploit the group encoding or invent a method that mostly uses the fastest of the group operations.

#################

# Compare pollard-rho vs pollard-kangaroo(lambda method*)

*parallel version rho resembles an image of the shape of the greek letter lambda, do not confuse!

*endomorphism have the constant is called lambda, do not confuse!

pollard-rho method effective for full field size Fp;

pollard-kangaroo method effective for partly field size Fp;

we can use rho for partly Fp, but runtime will remain as for full;

we can use kangaroo for full Fp, but it is about 1.60 times slower than rho; it becomes faster when b < 0.39p;

#################

# batch inversion, affine/jacobian, endomorphism, symmetry Y

Batch inversion is impossible.

Because its adding single points with pseudo random size step, instead total sequential compute.

"Are you using affine or jacobian coordinates for the points?"

its affine

# A + A -> A

# 1I, 2M, 1S

def add(P, Q, p=modulo):

R = Point()

dx = Q.x - P.x

dy = Q.y - P.y

if flag_gmpy2: # 1I, 1M

c = dy * gmpy2.invert(dx, p) % p

else:

c = dy * rev(dx, p) % p

R.x = (c*c - P.x - Q.x) % p # 1S

R.y = (c*(P.x - R.x) - P.y) % p # 1M

return R

But it's useless, we cannot economy multiples without batch inversion.

..how about using jacobian coordinates for adding points?

(to economy on inversions, 1I equal 20M, its very expensive)

One often uses projective coordinates to speed up elliptic curve arithmetic, so it is natural to use

projective coordinates when implementing these algorithms. But to define the pseudorandom walk one

needs a unique representation for points, so projective coordinates are not appropriate. See Remark 13.3.2.

test showed - X jacobian doesnt unique representation and distinguished points not found.

after convert J->A (only X) - all work, but -40% speed. conclusion - A+A->A is optimal. close.

Endomorphism is impossible.

Applying it to X coordinate is the same as changing discriminator(DP_rarity) - it will not give acceleration.

Speed depends only on number and size of jumps.

SymmetryY used in "three-kangaroo algorithm".

but 1.818w

^{1/2} vs 2w

^{1/2} very small speed-up efficiency. close.

SymmetryY used in "four-kangaroo algorithm"

1.714w

^{1/2} ..its (1.7/2)*100 = +15%. close.

lol, in python x*x*x*... more faster than x**y

and byte_shift 1<<123 more fastest (x10) than 2**123

#################

# popular questions

# I carefully read your posts in the thread and reply to them here

Why does the work suddenly increase (by a factor of about 8 to 10, depending on time or jumps)

why do you need 10 Ntimeit(N_tests)?

Algo of Pollard is probablistic nature (Birthday Paradox, Kruskal's card trick, etc)

The solution time is not stable; several attempts are needed to obtain the avg runtime and jumps.

..(heuristic time rather than deterministic)..

######

why need

pow2kang/kangoo_power = 3

its pow2 of number of kangaroos in herd T/W, affects max size jump, affects discriminator (DP_rarity)

######

pubkeys = {

, 33: ('02ed949eaca31df5e8be9bf46adc1dfae1734b8900dcc303606831372955c728da', False) #0x01abcd1234

,105: ('03bcf7ce887ffca5e62c9cabbdb7ffa71dc183c52c04ff4ee5ee82e0c55c39d77b', False)

..what does 3 column mean? And why do 33 and 105 matter False?..

it private key for double-check solution (demo/debug mode)

False if it unknow (recovery mode)

######

what i don't understand is , if 2^{50} bit address can be found in 570 second.

then why, we can't find 2^{105} bits of puzzle address in 1140 second? or bit more? but why it takes so much time than it should simply do...

105/50=2,1 ? not, wrong logic!

2

^{50} = 1125899906842624

2

^{105} = 40564819207303340847894502572032

2

^{105}/2

^{50} = 36028797018963968 times more?

..no, its square dependence - need sqrt: x

^{1/2}((2

^{105})

^{1/2}) / ((2

^{50})

^{1/2}) =

((40564819207303340847894502572032)

^{1/2}) / ((1125899906842624)

^{1/2}) =

6369051672525772 / 33554432 =

189812531 times more! its right result

and now if 2

^{50} found in 570sec, then 2

^{105} is

189812531 * 570 = 108193142670 sec = 3478y 5m 5d 10:44:30s

######

..multi pubkeys at once check inside bit range..

..this script check only 1 pubkey in bit range..

..but would it work does someone a test if multiple pub keys work?..

yes, only 1

"multi" check at the cost of "multi" drop in performance!

(if u dont know, break_short has the same problem on Gigant-step calc)

sry, but no

######

The Pollard-Kangaroo ... seems to find keys even when the specified bit size doesn't match the key mask, but it does take longer. I guess the bits parameter is a hint at where to start searching, rather than a maximum search space limit.

Pollard answers

If z is outside the interval, the algorithm will still work but will take longer.

#################

# cpu built

list add/fix:

- python2/3 compatibility (print/time/input/xrange/IntDiv)

- auto adaptation under environment

- some checks, debug, more info, minor accelerate

- (un)compress/custom/random pubkey

- format time: 0y 0m 0d 00:00:00s 000ms

- format prefix SI: Kilo/Mega/Giga/Tera/Peta/Exa

- heuristic prognosis (avg)time and (avg)jump per bits

- repair kangaroos, that falls into the trap of same sequences

- location privkey in keyspace on the strip

- percent status progress, lost/left time

- support arbitrary range (keyspace) start:end

- profiles with pre-setting

now support only single core

ps: you can already use option 1) by running script in Ncores copies, manually spliting the search range

multicore dev status

1) naive parallelism, split equally the search range

- warning! the lowest efficiency (w/Ncores)

^{1/2} - in process, wait..

2) parallelism by Oorschot&Wiener

- norm efficiency w

^{1/2}/Ncores

- odd numbers U=V=2p+/-1, U+V<=Ncores

- has problem of collisions between members of the same herd

- in process, wait..

3) parallelism by Pollard (best choice)

- norm efficiency w

^{1/2}/Ncores

- coprime number U+V<=Ncores

- never problem of collisions between members of the same herd

- in process, wait..

Acceleration on several devices (i.e. with shared RAM) for 2) and 3) (w

^{1/2}/Ncores) can only be achieved using the pool.

Filtered distinguished points should be sent to the pool in a single hashtable.

secp256k1 dev status

- roadmap

https://bitcointalk.org/index.php?topic=5173445.msg52417175#msg52417175 - in process, wait..

ver 0.8, python2/3, raw/coincurve+cffi/gmpy2

The message exceeds the maximum allowed length (64000 characters).

source moved to github

https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo.pymy cpu benchmark libs

Algo: 1 Tame + 1 Wild with distinguished points, expected of 2w^(1/2) group operations

1core i5-2540, win7x64

python2x64

[lib#raw] 7.1K j/s

[lib#coincurve] 23.7K j/s

[lib#coincurve+cffi] 32.1K j/s

[lib#gmpy2] 73.7K j/s

python3x64

[lib#raw] 8.8K j/s

[lib#coincurve] 28.6K j/s

[lib#coincurve+cffi] 38.9K j/s

[lib#gmpy2] 80.3K j/s

my cpu heuristic prognose

Algo: 1 Tame + 1 Wild with distinguished points, expected of 2w

^{1/2} group operations

avg stat after 10tests

1core i5-2540, python37x64 + gmpy2, win7x64

[i] 73.6K j/s;..

...

[prognose] expected of 2w^(1/2) group operations

-------|--------/--------|---------------------------------/---------------------------------|

W |jump avg/2w^(1/2)| time avg/2w^(1/2) |

-------|--------/--------|---------------------------------/---------------------------------|

..

2^020 | 2.0K/ 2.0K | 0y 0m 0d 00:00:00s 025ms / 0y 0m 0d 00:00:00s 026ms |

..

2^030 | 63.6K/ 65.5K | 0y 0m 0d 00:00:00s 813ms / 0y 0m 0d 00:00:00s 838ms |

..

>2^031 | 90.0K/ 92.7K | 0y 0m 0d 00:00:01s 150ms / 0y 0m 0d 00:00:01s 185ms |

..

2^035 | 359.9K/ 370.7K | 0y 0m 0d 00:00:04s 602ms / 0y 0m 0d 00:00:04s 740ms |

..

2^040 | 2.0M/ 2.1M | 0y 0m 0d 00:00:26s 034ms / 0y 0m 0d 00:00:26s 818ms |

..

2^050 | 65.1M/ 67.1M | 0y 0m 0d 00:13:53s 115ms / 0y 0m 0d 00:14:18s 187ms |

..

2^060 | 2.1G/ 2.1G | 0y 0m 0d 07:24:19s 701ms / 0y 0m 0d 07:37:41s 989ms |

..

2^070 | 66.7G/ 68.7G | 0y 0m 9d 20:58:30s 442ms / 0y 0m 10d 04:06:23s 669ms |

..

2^080 | 2.1T/ 2.2T | 0y 10m 15d 23:12:14s 170ms / 0y 10m 25d 11:24:37s 429ms |

..

2^090 | 68.3T/ 70.4T | 28y 1m 0d 22:31:33s 441ms / 28y 11m 5d 05:07:57s 730ms |

..

2^100 | 2.2P/ 2.3P | 898y 9m 0d 00:49:50s 128ms / 925y 9m 16d 20:14:47s 376ms |

..

2^105 | 12.4P/ 12.7P | 5.1Ky 1m 5d 09:19:00s 091ms / 5.2Ky 1m 5d 02:20:27s 505ms |

#################

# anomaly detected

~~The claimed avg "expected of 2w~~^{1/2} group operations" is not achievable with m = w^{1/2}/2 (mean jump size from acticles by Pollard)~~Empirical tests have shown that 2w~~^{1/2} is achievable at m * 8.all norm after add

# get pow2Jmax

def getPow2Jmax(optimalmeanjumpsize):

if flag_debug > 1:

print('[optimal_mean_jumpsize] %s' % optimalmeanjumpsize)

sumjumpsize = 0

for i in range(0,257):

sumjumpsize += 2**i

#sumjumpsize = (2**(i+1))-1

meanjumpsize = (sumjumpsize//(i+1))+1

if flag_debug > 1:

print('[Njumps#%03d] mean_jumpsize = sumjumpsize/Njumps = %s/%s = %s' % ((i+1), sumjumpsize, (i+1), meanjumpsize ))

if meanjumpsize >= optimalmeanjumpsize:

if flag_debug > 1:

print('[i] pow2Jmax=%s (%s >= %s)' % (i+1, meanjumpsize, optimalmeanjumpsize))

return i+1

#################

# gpu built (cuda/opencl)

Tank, I need a pilot program for a ~~V-212 helicopter~~ cuda/opencl.. Let’s go.

https://bitcointalk.org/index.php?topic=1306983.msg51796187#msg51796187https://imgur.com/a/f3zTmTathank you, it helped a lot

i imagine how j2002ba2 read topic and thinks

omg, he used python.. what a primitive primate..

https://github.com/beranm14/pollard_rho/tree/master/cuda_v1in process, wait..

#################

# parallelism problems

Maybe you can split equally the search range among threads ...

Pollard answers

6. The Kangaroo Method on a Parallel Computer

..A bad method is to divide the interval [L, U] into P equal parts, and use each of P processors(cores) to search one part, using the serial method. This will take time O((w/P)^{1/2})..

van Oorschot and Wiener [11] employ two herds of kangaroos in a method which runs in time O((w^{1/2})/P)..

i.e. if have P cpu and split equally the search range, than speed-up only P

^{1/2}..The lambda method suffers the same parallelization problem as the rho method..

Note that here each parallel processor is producing its own sequence of points independently of the others and each particular processor

does not increase the probability of success of any other processor.

..m cores have m^{1/2} accelerate..

..Suppose that there are P identical artists.

If we use P different sequences (that is, different polynomials F(x)), then the probability that the first k numbers in these sequences will be different modulo p will be approximately equal to exp ((-k^2P)/2p). Thus, the maximum acceleration can be estimated as P^{1/2}..

One important property of the lambda method is the fact that it is easily distributed on several computers. Each participant in distributed computing selects a random number r and begins to take pseudo-random steps from the number b^r, where b is the element of the group for which a discrete logarithm is sought. Each participant uses the same easily computable pseudorandom function f(G)->S, where S is a relatively small set of numbers with an average value comparable to the size of a group G of order n. The powers a^s for S are calculated in advance..

...

A small difficulty is that a match can occur within the same sequence. However, if the number of participants in the calculations is large enough, then the probability of a match between sequences is greater than the probability of a match within one sequence.

...

The central computer must track all sequences from all participants to identify matches. According to the birthday paradox, a match is expected when the number of elements in all sequences is of the order of O(N^{1/2}). Obviously, in the described form, this method requires a large expenditure of memory of the central computer. The following idea, described by van Orschot, greatly reduces memory requirements and thus makes this method applicable to solving complex problems. The idea is to consider the so-called selected points. It is assumed that the elements of the group are represented by integers (or, possibly, sets of integers). A distinguished binary field of length k in this number will consist of zeros of about (1/2)k of the entire time. A random walk will go through such marked points on average every 2^{k} steps. If two random sequences intersect somewhere, then they will intersect further and together will get to the next selected point. So, the idea is to send only these dedicated points to the central computer, which will reduce the required memory size by 2^{k} times.

There are two versions of the distributed algorithm, one by van Oorschot and Wiener [473] and another by Pollard [488].

The difference is how they handle the possibility of collisions between kangaroos of the same herd.

The former has a mechanism to deal with this, which we will explain later. The latter paper elegantly ensures that there will not be collisions between individuals of the same herd.

Van Oorschot and Wiener Version

..kangaroos are spaced a (small) distance s apart..

..If there is a collision between two kangaroos of the same herd then it will eventually be detected when the second one lands on the same distinguished point as the first.

In [473] it is suggested that in this case the server should instruct the second kangaroo to take a jump of random length so that it no longer follows the path of the front kangaroo.

Note that Teske [606] has shown that the expected number of collisions within the same herd is 2, so this issue can probably be ignored in practice.

Pollard Version

Let N be the number of processors and suppose we can write N=U+V where gcd(U,V)=1 (i.e. U,V is prime numbers) and U,V = N/2.

The number of tame kangaroos is U and the number of wild kangaroos is V.

The (super) kangaroos perform the usual pseudorandom walk with steps {U*V*u0,...,U*V*u(n-1)} having mean m=N(w^{1/2})/4

(this is UV times the mean step size for solving the DLP in an interval of length w/UV =~ 4w/(N^{2}).

As usual we choose either uj=2^{j} or else random values between 0 and 2m/UV.

The U tame kangaroos start at g^{(w/2)+i*V} for 0 <= i < U.

The V wild kangaroos start at hg^{j*U} for 0 <= j < V.

Lemma 14.6.5. Suppose the walks do not cover the whole group, i.e., 0 <= an < r (r is order).

Then there is no collision between two tame kangaroos or two wild kangaroos.

There is a unique pair of tame and wild kangaroos who can collide.

#################

How Bitcoin works, a simple explanation.

Private Key is the number N (very large, 2

^{256}, so that it is impossible to guess or count).

The Public Key is the point (x, y) on the ec curve type "secp256k1".

privkey is primary, and pubkey is computed from it. They exist in pairs.

Knowing the pubkey is almost impossible to restore its privkey. This is where safety is based.

There is a basic-point (i.e. basic-pubkey but don’t say that), everyone knows it, and the privkey for this point is 1.

To calculate pubkeyX from privkey = X, multiply basic-point by X.

#################

# How pollard-kangaroo works, the Tame and Wild kangaroos, is a simple explanation.

Suppose there is pubkeyX, unknow privkeyX, but privkeyX is in range w=[L..U]

The keys have a property - if we increase pubkey by S, then its privkey will also increase by S.

We start step-by-step to increase pubkeyX by S(i), keeping sumX(S(i)). This is a Wild kangaroo.

We select a random privkeyT from range [L..U], compute pubkeyT.

We start step-by-step to increment pubkeyT by S(i) while maintaining sumT(S(i)). This is a Tame kangaroo.

The size of the jump S(i) is determined by the x coordinate of the current point, so if a Wild or Tame kangaroo lands on one point, their paths will merge.

(we are concerned with pseudo random walks whose next step is determined by the current position)

Thanks to the Birthday Paradox (Kruskal's card trick), their paths will one day meet.

Knowing each traveled path, privkeyX is calculated.

The number of jumps is approximately 2*(w^1/2) group operations, which is much less than a full search w.

#################

# articles

(links from other users, all in one place)

base

https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/hand translate to ru/ua (recommend instead translate.google)

https://habr.com/ru/post/335906/0) best of the best, all in 1, epic, 2012

Chapter 14. Factoring and Discrete Logarithms using Pseudorandom Walks

https://www.math.auckland.ac.nz/~sgal018/crypto-book/ch14.pdf1) with reference to old

J. M. Pollard, “Kangaroos, monopoly and discrete logarithms,” Journal of Cryptology, #13 (2000).

https://web.northeastern.edu/seigen/11Magic/KruskalsCount/PollardKangarooMonopoly.pdf(good dir web.northeastern.edu/seigen/11Magic/KruskalsCount/)

2) about parallelism problems

P. C. van Oorschot and M. J. Wiener, Parallel collision search with cryptanalytic applications, J. Cryptology, #12 (1999)

https://people.scs.carleton.ca/~paulv/papers/JoC97.pdfadvice acceleration tips by fernand77

https://github.com/JeanLucPons/VanitySearch/issues/25#issuecomment-509293732#################

# polard implementations

(links from other users, all in one place)

kangaroo (now no info), by BurtW, (openssl,secp256k1?)

https://bitcointalk.org/index.php?topic=5173445.0kangaroo (classic, not use distinguished points), by natmchugh, python

https://bitcointalk.org/index.php?topic=5166284.msg52233957#msg52233957python, rho

rho, by Andrea Corbellini

github.com/andreacorbellini/ecc/blob/master/logs/pollardsrho.py

rho, by qubd

raw.githubusercontent.com/qubd/mini_ecdsa/master/mini_ecdsa.py

rho, by David Cox 2016

gist.github.com/davidcox143/c68a477b8390f35cb9a19084edd2a1e5

rho, by ralphleon

github.com/ralphleon/Python-Algorithms/blob/master/Cryptology/pollard.py

rho, by thomdixon

gist.github.com/thomdixon/dd1e280681f16535fbf1

other lang

github.com/nikitaneo/rho_pollard

github.com/twjvdhorst/Parallel-Pollard-Rho/

github.com/beranm14/pollard_rho/

github.com/grouville/factrace/

#################

# motivation

..they don`t want to share the tools like Pollard kangaroo script..

..Well, I’m gonna go build my own theme park, with blackjack and hookers!..

#################

why not use endomorphism for pollard-rho?

point after multiplying by beta is enough pseudo random?

if I'm right, this will be a new superfast method to calculate pollard-rho at the cost of 1M per 1 point

didn’t it occur to anyone before me, I need to test

#################

to be continued..