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 Oct 09 2019, edit#34
#################
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
coincurve+cffi: 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 = rM , 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 ygb+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.28w1/2 group operations
minimal RAM
2) use distinguished points
..The kangaroo method (of [11, p. 13]) can solve in about 2w1/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/2pollard-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/21) 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.
The idea is of course to only make sqr(2^(bit-2)) operations.
nice idea by st0ffl about x2 boost used SymmetryY
https://bitcointalk.org/index.php?topic=5173445.msg52616670#msg52616670lol, 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)..
######
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 250 bit address can be found in 570 second.
then why, we can't find 2105 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 build
Python implementation:
- python2/3 compatibility (print/time/input/xrange/IntDiv)
- auto adaptation under environment
- raw python/coincurve+cffi/gmpy2
- 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
Python multicore implementation:
1) naive parallelism, split equally the search range
- warning! the lowest efficiency (w/Ncores)
1/22) parallelism by Oorschot&Wiener
- norm efficiency w
1/2/Ncores
- has problem of collisions between members of the same herd
3) parallelism by Pollard (best choice)
- norm efficiency w
1/2/Ncores
- coprime/odd numbers U=V=2p+/-1, U+V<=Ncores
- without problem of collisions between members of the same herd
*you can already use option 1) by running script in Ncores copies, manually spliting the search range
*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.
*removed support coincurve lib, reason: if u can install coincurv - that u can install gmpy2
python multicore cpu, python2/3, raw/gmpy2
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo-multi.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] 24.5K j/s
[lib#coincurve+cffi] 35.4K j/s
[lib#gmpy2] 89.4K j/s
python3x64
[lib#raw] 8.9K j/s
[lib#coincurve] 31.2K j/s
[lib#coincurve+cffi] 43.2K j/s
[lib#gmpy2] 97.8K j/s
1core i7-6820
python3x64
[lib#gmpy2] 174.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] 97.8K j/s;..
...
[prognose] expected of 2w^(1/2) group operations
-------|--------/--------|---------------------------------/---------------------------------|
W |jump avg/2w^(1/2)| time avg/2w^(1/2) |
-------|--------/--------|---------------------------------/---------------------------------|
..
2^020 | 1.8K/ 2.0K | 0d 00:00:00s 018ms / 0d 00:00:00s 020ms |
..
2^030 | 57.3K/ 65.5K | 0d 00:00:00s 586ms / 0d 00:00:00s 670ms |
>2^031 | 81.1K/ 92.7K | 0d 00:00:00s 829ms / 0d 00:00:00s 948ms |
2^032 | 114.6K/ 131.1K | 0d 00:00:01s 173ms / 0d 00:00:01s 341ms |
..
2^040 | 1.8M/ 2.1M | 0d 00:00:18s 777ms / 0d 00:00:21s 471ms |
..
2^050 | 58.7M/ 67.1M | 0d 00:10:00s 886ms / 0d 00:11:27s 086ms |
..
2^060 | 1.9G/ 2.1G | 0d 05:20:28s 355ms / 0d 06:06:26s 759ms |
..
2^070 | 60.1G/ 68.7G | 7d 02:55:07s 378ms / 8d 03:26:16s 292ms |
..
2^080 | 1.9T/ 2.2T | 7m 17d 21:23:56s 096ms / 8m 20d 14:00:41s 355ms |
..
2^090 | 61.5T/ 70.4T | 20y 3m 2d 12:45:55s 095ms / 23y 1m 28d 16:22:03s 390ms |
..
2^100 | 2.0P/ 2.3P | 648y 2m 21d 00:29:23s 067ms / 741y 2m 17d 19:45:48s 481ms |
..
2^105 | 11.1P/ 12.7P | 3.7Ky 10m 29d 06:43:07s 581ms / 4.2Ky 11m 12d 16:12:57s 514ms |
..
2^110 | 63.0P/ 72.1P | 20.7Ky 2m 12d 15:40:18s 166ms / 23.7Ky 11m 0d 08:25:51s 416ms |
..
2^120 | 2.0E/ 2.3E | 663.8Ky 5m 14d 21:29:41s 312ms / 759.0Ky 4m 11d 05:47:25s 328ms |
----------------------------------------------------------------------------------------------
C99 implementation
- singlecore
- bitcoin-core/secp256k1 library
- A+A->A; 0.219M j/s (1core i5-2540)
https://bitcointalk.org/index.php?topic=5173445.msg52473992#msg52473992C++ implementation
- multicore
- based on engine VanitySearch1.15, vs bignum lib
- A+A->A; 0.175M j/s (1core i5-2540)
https://bitcointalk.org/index.php?topic=5173445.msg52698284#msg52698284#################
# GPU build (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..
article cuda + pollard-rho
https://github.com/beranm14/pollard_rho/blob/master/report/main.pdfrho, by brichard19, good candidate to rewrite
https://github.com/brichard19/ecdlroadmap:
- rewrite VanitySearch to pollard-kangaroo
in 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((w1/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 m1/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 P1/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(N1/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 2k 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 2k 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(w1/2)/4
(this is UV times the mean step size for solving the DLP in an interval of length w/UV =~ 4w/(N2).
As usual we choose either uj=2j 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 hgj*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#msg52233957rho, by brichard19
github.com/brichard19/ecdl
python, 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..
