y, now some show

You have funny memory problems (as -d 42).
I remind you that I got zero because you did not fulfill your part of the contract.
It was a simple job and (simultaneously) checking you for competence and honesty.
You failed miserably. Work with you? It’s useless to talk to you. Your word is zero, sad but true.

Read more about the events of September 2019.
VanitySearch1.17fix successfully adapted for vanitypool.appspot.com
Agreed, my fix, u gpurigs, 50/50.
Just on the calculated day, the reward leaves the account.
..And zielar disappears for a month! (wow, nice coincidence, y?)
Upon returning, he declares that he has nothing to do with the transaction!
Ok, look at the blockchain:
#60: 1Kn5h2qpgw9mWE5jKpk8PP4qvvJ1QVy8su -> 14yX9jrgmtJByn5YSTdA2uZM6kFQ9z9BUu -> 35HzrskKgRekhB9RgFGNrfhNbdqC1PvEUL
#61: 1AVJKwzs9AskraJLGHAZPiaZcrpDr1U6AB -> 13aNcjjyQYgQZxnxz6Ar9eRqQENexDBPjh -> 35HzrskKgRekhB9RgFGNrfhNbdqC1PvEUL
#62: 1Me6EfpwZK5kQziBwBfvLiHjaPGxCKLoJi -> bc1q055ws5xnrnjtf767cxuklrjl8vw5sst2j4a9lm -> 35HzrskKgRekhB9RgFGNrfhNbdqC1PvEUL
#63: 1NpYjtLira16LfGbGwZJ5JbDPh3ai9bjf4 -> bc1qdqtkkmwtxk5ce0xvp57k46hnx8t43ngw97twmx -> 35HzrskKgRekhB9RgFGNrfhNbdqC1PvEUL
and..
1ThePiachu -> 18A3UeLrcJbi58jci1s7xQss8v8QK8YJPK -> 1JSVnxtzLxNpW6YkXQbV1guW6FdZAaKM4L -> 35HzrskKgRekhB9RgFGNrfhNbdqC1PvEUL
Tadaaa!
Even if 35HzrskKgRekhB9RgFGNrfhNbdqC1PvEUL does not belong to zielar..
..already in the third transfer, money RANDOMLY passes through this wallet.
And here I have to believe that zielar has nothing to do with what is happening)))
Its epic, really.

Open eyes. This is either you or your partner (the one you trust).
And, probably, the events in January are connected with this.

The truth is somewhere nearby, but I still will not see my piece of money.
So by right of verification I declare once again to everyone - be careful with zielar.

Some "unusable sticky thing" by me
https://github.com/Telariust/VanitySearch-appspot/releases
https://github.com/Telariust/VanitySearch-bitcrack/releases
danger! very unusable)


y, brutal insolent)


this phrase very expresses the attitude of the hero to the people around him.
if you google it, this is not the first time he has said this.
lack/ignore of arguments and explosive emotionality. love it


Apparently, brichard19 also refused twice. Five times in a row.
(I recall how he answered in issues that he could not improve the program because he did not have enough money for a modern video card. But who read issues?)
Oh, it simple, BitCrack is also a "sticky thing", and brichard19 needs "get to work better", y.


y, i have big complex. intolerance of irresponsible people


i say, how about transfer to brichard19, let be 10% of #59-63, ~=0.35BTC
Transfer, if there is still something to keep.

Gentlemen, the time of bets - is whether the transfer will take place or if there will be another excuse.


..When the world record is set, remember, at what cost.

It is time for those present to take off the pink glasses.

Yes, definitely. No less than you for #59, #60, #61, #62 and #63.
Half. From ZERO.

Half. From ZERO.

Guess, what be.

Guess, what answer.
ZERO (it's not even his equipment)

God, he can't even run someone else's program.

Congratulation and nice job
https://www.youtube.com/watch?v=q6mMh4pRki8

Babbler only. Be careful with him.


30 days.. 30 pages.. want news? doubling Ygrid gives +25% speed

in hashtable
ok, i will add output to file distinguished points in next release.
there is only one practical use for saving points to disk - distributed enumeration on different devices without a pool.
I myself plan to do so, since writing a pool is much more difficult than collecting a save once a day.

x2 speed-up, nice idea, i will add as option of boost in next release

the formula calculates a number of points about 10 pieces per kangaroo for 100% of the lead time, taking into account the size of the range.
Now the overflow of the table will occur with a probability of 50% if launched on 96 cores or more. It needs to be fixed.

1) Algo of Pollard is probablistic nature (Birthday Paradox, Kruskal's card trick, etc)
The solution time is not stable; several attempts (timeit loop in python script) are needed to obtain the avg runtime and jumps.
heuristic time rather than deterministic

2) threads should run at equal speed.
If input -t N over than really N cores, so threads will compete, some will be faster and some will be left behind.

3) maybe my code have bug, need more tests

#################
post dedicated cuda/opencl implementations

we have some ways for just ready GPU implement
good candidates to rewrite:

1) cuda, c++, VanitySearch,  by Jean_Luc
https://github.com/JeanLucPons/VanitySearch

2) cuda/opencl, c++, BitCrack, by brichard19
https://github.com/brichard19/BitCrack

2) cuda, python, pollard-rho, by brichard19
https://github.com/brichard19/ecdl

3) cuda, ?, pollard-rho
github.com/beranm14/pollard_rho/

4) opencl, C#, pollard-rho
github.com/twjvdhorst/Parallel-Pollard-Rho/

I intend to evaluate their performance, as well as rewrite one or more to kangaroo.

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

multicore, CPU only, c++, based on engine VanitySearch1.15
https://github.com/Telariust/vs-kangaroo/releases

bignum lib by Jean_Luc is good, only %15 slower than bitcoin-core/secp256k1 lib (with raw asm mult)


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

not

BitCrack use batch packet inversion (x8 speed-up).
We cant(OR CAN?..) use its in kangaroo method, so 1430/8 = 175M j/s

but on screen
see 4xV100=6515M j/s, each 1600M j/s

now unclear..

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

https://bitcointalk.org/index.php?topic=1306983.msg48224432#msg48224432
November 25, 2018 this man speaks as if he already has a finished implementation.


O great master, j2002ba2, I urge you!   Plz, come and explain to the miserable mortals, which means s2,s1,m3,m4 in your program!

#################
https://docs.nvidia.com/cuda/volta-tuning-guide/index.html
he high-priority recommendations from those guides are as follows:
 - Find ways to parallelize sequential code;
 - Minimize data transfers between the host and the device;
 - Adjust kernel launch configuration to maximize device utilization;
 - Ensure global memory accesses are coalesced;
 - Minimize redundant accesses to global memory whenever possible;
 - Avoid long sequences of diverged execution by threads within the same warp;


about last, " - Avoid long sequences of diverged execution by threads within the same warp;"
parallelism algo by Pollard (U+V) escape problem of collisions between kangaroos of the same herd;
this allows you to completely abandon the correction block because adding IF () inevitably breaks the parallelism of the GPU;

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

to be continued..

talk less, work more... my C99 prototype ready!
everything is exactly as I described above

1core i7-6820, win7x64

// MODE: J + A -> J,  xJ->xA   ; 0.23Mk/s; secp256k1_gej_add_ge_var(), convert only X jacobian to affine
40bits, w=39bit, 2w^(1/2) at 17sec


// MODE: 1*J+k*G->J, xJ->xA   ; 0.09Mk/s; secp256k1_ecmult(), convert only X jacobian to affine
40bits, w=39bit, 2w^(1/2) at 43sec


// MODE: k*G->J, J+J->J, xJ->xA; 0.03Mk/s; secp256k1_ecmult_gen() + secp256k1_gej_add_var() , convert only X jacobian to affine
40bits, w=39bit, 2w^(1/2) at 127sec

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

Ok! I will publish a little later, need to tidy the code.

github.com/Telariust/pollard-kangaroo-c99/releases/
Enjoy!  

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



Affinity A + A-> A ready.
Real growth was about 6-8% (probably 20M per 1I from the article is overpriced)

runing test, task is 50
1core i7-6820, win7x64

[algo#1]   J + A -> J,  xJ->xA   ; secp256k1_gej_add_ge_var()

[algo#0]   A + A -> A,  xA ready ; the fastest!

runtime:    556/522 = x0.065 (+6,5%)
hashrate: 0.29/0.27 = x0.074 (+7,4%)

miserable improvement, less statistical error... certainly better than nothing;
but checked the hypothesis A+A->A;


Short compare algoritms:
1core i7-6820, win7x64


ready-made, if someone needs it.
Affine points addition, custom functions, C99, bitcoin-core/secp256k1
2A -> A (1I, 2M, 2S)
A + A -> A (1I, 2M, 1S)

From https://www.nayuki.io/page/elliptic-curve-point-addition-in-projective-coordinates

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

and now we have the answer

ver0.1 C99, win7x64, algo A+A->A
1core i7-6820
0.291Mk/s
1core i5-2540
0.219Mk/s

ver0.9 python37x64+gmpy2, win7x64, algo A+A->A
1core i7-6820
174.3K j/s;
1core i5-2540
99.7K j/s;

.. why the name of this function is not familiar to me? (although I used multiplication) .. and why I myself didn’t feel the need to write a*b+c ?..
i looked at my source code - always use
// R = na*A + ng*G
// secp256k1_ecmult(*ctx, gej *r, const gej *a, const scalar *na, const scalar *ng);
I bet your experiments with ECMULT_WINDOW_SIZE didn’t give anything, because secp256k1_ecmult_gen() doesn’t use it  
I used exactly secp256k1_ecmult() because it is accelerated in ECMULT_WINDOW_SIZE.
moreover, secp256k1_ecmult() uses endomorphism to accelerate multiplication (but only if you use both na*A+ng*G, not one of them)

also why _ecmult() more faster than _gen()
https://github.com/bitcoin-core/secp256k1/pull/41
https://github.com/bitcoin-core/secp256k1/pull/210#issuecomment-96145070
https://github.com/bitcoin-core/secp256k1/pull/210#issuecomment-96166989

simple init for secp256k1_ecmult()

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

I was interested to compare these functions.

1core i7-6820
secp256k1 (now, without endomorphism)

default ECMULT_WINDOW_SIZE = 15

########

Test#1, multiplication, increment sequential points, calculation 1million pubkeys in loop:


results of benchmark

1M at 58,0 sec; 0,017Mk/s
constant-time? hoho)

1M at 26,5 sec; 0,037Mk/s
.. against timing attacks? y, its need rewrite, its right.

1M at 8,2 sec; 0,121Mk/s

same function, another
1M at 3,5 sec; 0,285Mk/s
now u can see, how efficiency working ECMULT_WINDOW_SIZE (because we calculation sequential points)


secp256k1_ecmult() (option "0*P0 + K*G") - best choice (x7.5 faster than secp256k1_ecmult_gen() for multiply sequential points)


########

Test#2, multiplication,  pseudo random points, calculation 1million pubkeys in loop:


results of benchmark

1M at 58,5 sec; 0,017Mk/s
same

1M at 26,5 sec; 0,037Mk/s
same

1M at 16,4 sec; 0,061Mk/s
diff! slower

same function, another
1M at 9,5 sec; 0,105Mk/s
diff! slower
efficiency lower, ECMULT_WINDOW_SIZE working is not so good (because we calculation pseudo random points)


secp256k1_ecmult() with "0*P0 + K*G" - best choice (x2.8 faster than secp256k1_ecmult_gen() for multiply pseudo random points)


########


Test#3, addition points, calculation 1million pubkeys in loop:


results of benchmark

1M at 0sec 337msec; 2,9Mk/s

1M at 0sec 285msec; 3,5Mk/s
3,5Mk/s, Karl!

1M at 0sec 183msec; 5,4Mk/s
(its double, rarely used)


secp256k1_gej_add_ge_var() - best choice (x33.3 faster than secp256k1_ecmult(), x92.9 faster than secp256k1_ecmult_gen())


https://github.com/Telariust/pollard-kangaroo-c99/blob/master/compare-test.c

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.
I ask you to check on your implementation what speed will be if the MID/MAX step size is increased by 8 times, plz.
thx, no need
all norm after add

#################
about speed

no, absolutely not

August 26, 2019
Standard OpenSSL library averaged 1897 hops per second    
secp256k1 (S 8X32, F 10X26) averaged 5258 hops per second  

September 09, 2019 (secp256k1)
already better, but..

it very slow for 1core C/C++ openssl/secp256k1, it should be more!
(even if u built early classic 1 Wild algo with 3.28w^(1/2), this does not explain x10 speed drop)

ok, we expect and hope

see for compare

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

1core i5-2540, python37x64, win7x64
(it raw python!)

1core i5-2540, python37x64 + gmpy2, win7x64

#################
about secp256k1 library

Legendary main question from legendary master    root of all ecc problems)
42: Answer to the Ultimate Question of Life, the Universe, and Everything"

secp256k1 have functions J+J->J , J+A->J , and no have functions A+A->A (Is this a precisely optimized library for bitcoin? )
(all simple, because in real often need multiply rand point instead adding, and jacobian is better for multiply)
J+J->J (12M, 4S) - bad choice
J+A->J (8M, 3S) - already better
(look eprint.iacr.org/2016/103.pdf)
you can take the code from break_short by Jochen Hoenicke, it fits perfectly.
this code uses J+A->J and convert only X to Affine xJ ->xA (its max what we have in secp256k1 as it is)
where A is S-table with pre-computed G,2G,4G,8G,16G..
..u used pre-computed, y? not say me what u calc every Si permanently used multiplication, nonono,plz,no! X%mask instead pow2(X%k)?
(..by the way, that would explain your terrible speed..)
..and use old alternatively functions without protection against side channel attacks, +10-20% speed
secp256k1_gej_add_ge_var() instead secp256k1_gej_add_ge()
(warn, _var() need normalize before use in some functions.. my early mistake, "leading zeros" github.com/bitcoin-core/secp256k1/issues/601)
in ideal - need write new functions:
A+A->A (1I, 2M, 1S) - best choice, because in the end we need X in affine for unique representation each point to adding in storage hashtable
..u used hashtable, y?)
after which do not need to spend 8M,3S, only nearly 20M to each 1I, it +35% speed-up
like that

########
I seem to know what the problem is.
This is a very obvious fact for me, I should have started with it.
(I should have guessed at a time when about ECMULT_WINDOW_SIZE)

No multiplies the points inside the loop!
I warn, multiplication points is very expensive, more expensive than the slowest addition points.
Shouldn't use it at all in multi-million integration cycles.
You must calculate all possible displacement points before the start of the cycle.
Then just add them, being inside cycle.

I think you are using a mask
https://bitcointalk.org/index.php?topic=5166284.msg52068840#msg52068840
..so you can’t store several million pre-calculated points in memory. it explains your choice.
not mask, i see,.. then simple, u tried built classic pattern of a*b+c

I tell you - take loop from break_short as it is (with standart functions), rewrite to kangaroos, and benchmark it.
if after you still want to rewrite what, then ok (but i think what not)
I think the "secret sauce" will not create, it will turn out an exotic slow implementation through multiplication.
I would like to be mistaken, but my experience says that you lose time.
..How do I know about multiplication?.. I checked it myself,.. and from the topic about why brainflayer is slow and why it cannot be done faster,.. and it was on one of the topics pages LBC.
This is not the most famous fact, it is not surprising that you did not know about it, no fault.

Its not random, not brainflayer,  its pseudo random walk, so we can pre-compute our jumps size (offset points) for using addition points instead multiplication points.

https://bitcointalk.org/index.php?topic=5166284.msg52318676#msg52318676


I also thought so for a long time.
not really if the size does not exceed 49152
VanitySearch restarts the kernel about 1000 times per second (!!!), and it works fine.
opencl unknow

..and this is one of the main technical reasons why gpu BF do not.
cpu BF checks huge dictionaries in a few hours. loading such volumes into gpu is problematic.
therefore gpu BF should work using the built-in generator, e.g. brute force seed.

True, according to my knowledge after 1 year of research.

In fact, you want a gpu BrainFlayer. Everyone wants it)
Ryan refuses to write it because he is a WhiteHat.

If successful, it will be slower than sequentially calculating points.

##########################
heuristic calculate the hashrate for BrainFlayer cuda/opencl

BrainFlayer cpu sse
0,1 Mk/s - 1core i7-6820
8core - 4core real, 4core hyper-threading, so x6 instead x8
0,6 Mk/s - 8core i7-6820

VanityGen x64 opencl
60.7 Mk/s - gtx980
0,52 Mk/s - 8core i7-6820

60.7/0,52 = x116,7 (vg opencl gpu/cpu)

VanityGen x64 cpu sse
1,38 Mk/s - 8core i7-6820

1,38/0,52 = x2,6 (vg sse/opencl)

now if imagine
BrainFlayer opencl
0,6x(1/2,6) = 0,23 Mk/s - 8core i7-6820
0,23x116,7 = 26,8 Mk/s - gtx980

if
clBitCrack opencl
67.7 Mk/s - gtx980
cuBitCrack cuda
153.5 Mk/s - gtx980
241.3 Mk/s - gtx1070

153.5/67.7 = x2,26 (bc cuda/opencl)

then
BrainFlayer cuda
26,8x2,26 = 60,5 Mk/s  - gtx980
60,5x(241.3/153.5) = 94,9 Mk/s  - gtx1070

The Engine of these programs is divided into two types:

1) optimized point addition (for quick calculation of sequential keys)
 sample programs: vanitygen, bitcrack, vanitysearch, break_short;
 methods:
 - calc only X coordinates (for compressed keys);
 - use of functions without protection against side channel attacks (openssl/secp256k1);
main problem - inversion calculation is very expensive, ~20mult per 1 point;
can use batch inversion (Simultaneous algorithm, 1 inversion per 1000 keys) + Affines coordinates + symmetry(only full range) + endomorphism(only full range);

2) optimized point multiplication (for quick calculation of random keys)
 sample programs: brainflayer;
 methods:
 - secp256k1 library with pre-calculated mult table in ram;
 - Jacobian coordinates;
main problem random mult - inversion need too, but can not use batch inversion because each key is random.

BitCrack is optimized for sequentially calculating points in a limited range using addition.
VanitySearch is optimized for sequentially calculating points in the full range using addition (and 4 multiplication algorithms that work only for the full range).
BrainFlayer (cpu only) is optimized for random calculating points in a full range using multiplication.
You want to get random points in a limited range using multiplication.
These are fundamentally different tasks.

If you delve into the study of random generators, you will find that they have top speed.
Typically, the problem is that the overhead of generating random numbers is greater than the useful calculation itself.

PS:
about multiplication
At start BitCrack, pre-computes the starting points using multiplication.
It is so slow that starting from version 0.15 the author transferred the procedure to gpu.

see 1post - v0.0.6...  the author does not come here for more than a year

compare
and
see?

need new column - optimal argv
i know
# GTX1060  = -b 9 -t 512 -p 1024
# GTX1070  = -b 15 -t 512 -p 1024
# GTX1080Ti= -b 28 -t 512 -p 1024

and 2cols of hashrate - with default and with optimal argv

..and its good content for add to 1post

origin link
https://fe57.org/forum/thread.php?board=4&thema=1#1

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¹²³ == 2^(123) == 2**(123) == pow(2,123) == pow2(123) == 1<<123
sqrt(2) == 2^1/2 == 2**0.5

2¹²³ - 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
(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

..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

this is based of [5]

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:
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);
this reduces speed, jumps indicating norm, but really there are many calculation useless same sequences.
omg, but ok

#################
# Most famous optimizations of Pollard
# about complexity, runtime and RAM


why use distinguished points more efficiency

 "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
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.


#################
# 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.

its affine
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)
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.


nice idea by st0ffl about x2 boost used SymmetryY
https://bitcointalk.org/index.php?topic=5173445.msg52616670#msg52616670


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

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.
######
it private key for double-check solution (demo/debug mode)
False if it unknow (recovery mode)
######
105/50=2,1 ? not, wrong logic!
2⁵⁰  = 1125899906842624
2¹⁰⁵ = 40564819207303340847894502572032
2¹⁰⁵/2⁵⁰ = 36028797018963968 times more?
..no, its square dependence - need sqrt: x^1/2
((2¹⁰⁵)^1/2) / ((2⁵⁰)^1/2) =
 ((40564819207303340847894502572032)^1/2) / ((1125899906842624)^1/2) =
6369051672525772 / 33554432 =
189812531 times more! its right result
and now if 2⁵⁰ found in 570sec, then 2¹⁰⁵ is
189812531 * 570 = 108193142670 sec = 3478y  5m  5d 10:44:30s
######
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
######
Pollard answers

#################
# 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/2
2) 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.py


my cpu benchmark libs
Algo: 1 Tame + 1 Wild with distinguished points,  expected of 2w^(1/2) group operations
1core i5-2540, win7x64

1core i7-6820


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


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#msg52473992


C++ 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)


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

i imagine how j2002ba2 read topic and thinks


article cuda + pollard-rho
https://github.com/beranm14/pollard_rho/blob/master/report/main.pdf

rho, by brichard19, good candidate to rewrite
https://github.com/brichard19/ecdl

roadmap:
 - rewrite VanitySearch to pollard-kangaroo

in process, wait..

#################
# parallelism problems


Pollard answers
i.e. if have P cpu and split equally the search range, than speed-up only P^1/2






#################
How Bitcoin works, a simple explanation.

Private Key is the number N (very large, 2²⁵⁶, 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.pdf

1) 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.pdf

advice 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.0

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

rho, 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



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

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..

OpenSSL's advantage in versatility, but not in speed, no.

I bet python+coincurve will be faster!
ideally you need C bitcoin/secp256k1
I am porting your code to bitcoin/secp256k1 as soon as the source code is published.
(there is the usual addition and multiplication of points, nothing complicated)
(..but I feel you want to do it yourself, your own and not someone else's head?)

https://gist.github.com/natmchugh/e094232a3975b89bff2d

lol, not so simple

Its used import some old version(maybe clone) ecdsa library (there are also "class Point")
Also we can use raw.githubusercontent.com/andreacorbellini/ecc/master/logs/common.py
Also we can use raw.githubusercontent.com/qubd/mini_ecdsa/master/mini_ecdsa.py
(mini_ecdsa need some fix for python3)
(and it lib have own pollard-rho! but dont try run it for secp256k1, need custom ecc with low order! example look at homepage)
Also we can use the fastest coincurve github.com/ofek/coincurve

######

Fact: origin basepoint in code is currupted.. and origin value some exotics..

######

Its code is classic/early/not_optimized kangaroo

 - not use distinguished points
 - total run-time of approximately 3.28(w^(1/2)) group operations

######

Who cares, i builded 4 realease with each lib
www.sendspace.com/file/wdyg2o
here the fastest based coincurve
------------------------------------
update, add cffi, +30% speed
get X,Y using .point() is slow, cffi faster
------------------------------------

!!!!!
than
(auto-translate)
and googling "Probabilistic Bitcoin Mining Method"
What u know about this?
(given the probabilistic nature of the kangaroo, this can help)

y, it sad  


Just optimizing the compiler Cuda has gone a lot ahead.
Look for example: https://arxiv.org/ftp/arxiv/papers/1005/1005.2581.pdf

on the other hand... new release JohnTheRipper 1.9
https://www.openwall.com/lists/announce/2019/05/14/1

opencl trash? or Brichard19 need to train more?  unclear

python3 script success wrote and add to faq post:
bitcointalk.org/index.php?topic=4453897.msg52106273#msg52106273

if the checksum(or/and flag compress x01) is corrupted, than recovery now is impossible.
(--stride opt becomes float but must be integer!)
Recovery of these keys is possible only if brichard19 implements support float for --stride opt.

if it is easier to explain..
In WIFbase58privkey, each lost symbol(*/?) to the right is a division stride by 58.
Already from the middle, the stride no longer divides completely.
What does checksum have to do with it? In fact, the checksum forms the float part.
While it is equal, then when subtracting it is reset.
As soon as it becomes different for lowerKey and lowerKey+1, this indicates - stride becomes float.

Look to:

GPU/GPUEngine.h

try increase it to 256 or 512..

hashrate diff:
664/549 = x1,20
710/549 = x1,29

how about -g argv?
120x512=61440
480x128=64440
but it not equal:
-g is useless for it, recompilation is necessary
https://github.com/JeanLucPons/VanitySearch/files/3568897/VanitySearch-1.1.5_th128gr.orig.zip
https://github.com/JeanLucPons/VanitySearch/files/3568900/VanitySearch-1.1.5_th256gr.zip
https://github.com/JeanLucPons/VanitySearch/files/3568904/VanitySearch-1.1.5_th512gr.zip
recompiled, non-official build from me (while Jean_Luc thinks what to do)

ripemd160(base16) <--> btcaddr(base58) <--> Int/Dec(base10) <--> Hex(base16) <--> Binary(base2)
it's the same thing, just the bases are different, converting
..because main target(puzzle) assumes a public key unknown (only its ripemd160 hash is known).
and if pubkey is known then sequential key search in a limited space (which uses bitcrack) is the stupidest and slowest way to search compared to baby-step-gigant-step algo and pollard-rho/kangaroo algo
when BitCrack compute 10M keys, its checked 10M keys
when BSGS/Pollard compute 10M keys, its checked (10M)^2 = 100000000M keys (!!!..undestand?)

This fork https://github.com/pikachunakapika/BitCrack

Hi, dev ExploitAgency!

Look at:
https://github.com/exploitagency/vanitygen-plus/issues/205
origin link
https://bitcointalk.org/index.php?topic=25804.msg52110068#msg52110068
extended
https://bitcointalk.org/index.php?topic=25804.msg52124850#msg52124850

If u can and want (Last Active: November 26, 2017, 01:07:26 AM)..
It would be great if you released the official minimal update with fix opencl kernel, increased rekey_at, fixed auto-detection of the gridSize, and binary release is x32 and x64bit.

please, do not use quoting huge messages


in xxBitCrack.exe folder
u can direct run cmd shell in folder using trick: Shift+RightClickMouse -> Open Shell

https://github.com/brichard19/BitCrack/releases/tag/0.24


hmm.. it not u.

when I wrote this I wanted to demonstrate that this is generally possible.
Now I see that I did not take into account special cases ...
need to consider and complement
.. manually calculating this is inconvenient, it's time to write a script