Science Fair Project to trap Bitcoin private keys using Kangaroos!

j2002ba2

full member

Activity: 206

Merit: 447

Quote from: btc-room101 on April 22, 2021, 08:09:13 PM

Most success in ECDLP has been in Pollard-Rho, like a '6' character you following the tail until find the point of entry into a circle, but this method requires memory storage, but this method only works on TOY problems because there is not enough memory on earth to store the history.

You are mistaken. Pollard Rho & Kangaroo both use the same amount of memory (the same order of magnitude). In the original rho the whole memory is only two points and two numbers mod curve order. Parallelizing multiplies the needed memory, but it still remains insignificant compared to the number of point additions. The amount of memory needed is linearly dependent on the number of parallel computations.

btc-room101

member

Activity: 182

Merit: 30

Quote from: bounty0z on November 26, 2019, 12:03:51 PM

Hello,
any one here please can explain to me what mean by Wild and Tame ? , I know that they are hops of kangaroo, but how can I use them.
for example I want to know if i run pollard for #105 and get a Wild hop, but I shutdown the pollar code .. I don't want to start from the beginning so how can I import the Wild that I find in first ? ,and the same for Tame.

the second question is, what is tame and wild ? they are collision ? if yes and we can import them ,so we can just everyone poste the wild and tame that he find and we will find it quicly !!

Thanks

Even the inventor John Pollard regrets this name, this tech is some 40+ years old. Originally is was called Pollards's Rho/Lamba method, where Lamda is an upside down Y

The notion was that two different searches converge on a common point, leading to the end goal

Then historically Pollard was reading 'national geographic' on a story about kangaroo breeding in Austrailia, and decided to call lambda-method the Kangaroo method, it is complete bullshit, there is no abstraction or moral equivalence, or equivalent thinking here

Long ago, they used to call this crap baby-step/giant-step which is better, it all come out of the same people

The principal IDEA of Kangaroo is they HOP, they HOP BIG ( giant step ), they hop small ( baby step ), you jump around the finite-field ( your prime space, a big number )

Originally they kept all the hop history in memory, but of course that restricted the search, think 2^256 is 10^77, which is all the electrons in the universe, impossible to find this memory

So they came up with a method that didn't require lots of memory, which is this method the 'kangaroo' or 'lambda' method.

Jump around the field space, and if you find a Disctinct-Point you record it in memory, and you have 100's if not 1,000's of processes doing the same, if later another process hits that special-point, then all the kangaroos follow that point. So a DP is the 'Y' where the two top lines converge to make one.

Now the problem with DP is its not the real Lambda Point its just a special point, defined as you wish, sort of like mining bitcoin, where difficulty is set by the number of leading zeros on a hash, here the DP is the special point defined much the same way, its just a unique point that all processes can agree on; it doesn't mean that this is the true point of convergence, just means that its a "Point of Interest", randomly defined by humans. Under their rules.

So kangaroos hop around looking for a DP in giant-hops, and if a DP is found, then they incrementally search that point forward;

The problem with the Lambda method is its restricted to a tiny subspace of the field, if your doing btc which is 2^256, the jean-luc kangaroo algo only lets you choose a 2^20 field of view, so unless its a 'made up puzzle' problem in that 2^40 space, the likelyhood of solving the problem is zilch

Most success in ECDLP has been in Pollard-Rho, like a '6' character you following the tail until find the point of entry into a circle, but this method requires memory storage, but this method only works on TOY problems because there is not enough memory on earth to store the history.

alevlaslo

hero member

Activity: 1988

Merit: 593

Quote from: Telariust on September 16, 2019, 01:58:06 PM

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

Code:

C:\cygwin64\home\User\pollard-kangaroo>pollard-kangaroo.exe

[###########################################################]
[# Pollard-kangaroo PrivKey Recovery Tool #]
[# C99, bitcoin-core/secp256k1 library #]
[# singlecore #]
[# ver 0.1 #]
[###########################################################]
[DATE(utc)] 16 Sep 2019 18:23:53
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pow2bits] 2^40
[range] 2^39..2^40 ; W = U - L = 0x0000008000000000 (2^39)
[maxDP] 1024 (max elements in hashtable)
[DPmodule] 0x0000000000040000
[pow2Jmax] 23
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
--> TEST MODE
[pubkey(tests)] 03A2EFA402FD5268400C77C20E574BA86409EDEDEE7C4020E4B9F0EDBEE53DE0D4
--> pubkey valid!
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] Sp-table of pow2 points - ready
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] T1+W1 herds - ready
--> [0y 0m 0d 00:00:06s] [0.23Mk/s] [0y 0m 0d 00:00:11s]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[i] 1700051j; DP T+W=4+3=7; dp/kgr=3.5;
[prvkey#40] 000000000000000000000000000000000000000000000000000000E9AE4933D6
[#############################; passtime: 0y 0m 0d 00:00:06s]
[####################################; precision: 6s 38ms]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[DATE(utc)] 16 Sep 2019 18:23:59
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[x] EXIT

40bits, w=39bit, 2w^(1/2) at 17sec

Puzzle 32 how many time?

https://bitcointalksearch.org/topic/m.55448862

dextronomous

full member

Activity: 431

Merit: 105

ok great to have had you around. bye

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

As you can probably guess my daughter lost interest in this project and she moved on to other things: competitive rock climbing, learning to fly an airplane, collecting vinyl records (!), learning to play the bass guitar in her own rock and roll band, etc. Oh to be 13 again...

brainless

member

Activity: 348

Merit: 34

Quote from: Btchunter3333 on February 28, 2020, 04:18:24 PM

If i have 10 PC with different cpu cores numbers, how i can setup the program to search for same private key but on different range and to run program on all PC?

PC 1 to search for 10% of private keys PC 2 for next 10% and so on and the last for last 10%?

try now gpu version for Kangaroo
https://github.com/JeanLucPons/Kangaroo

Btchunter3333

full member

Activity: 486

Merit: 102

If i have 10 PC with different cpu cores numbers, how i can setup the program to search for same private key but on different range and to run program on all PC?

PC 1 to search for 10% of private keys PC 2 for next 10% and so on and the last for last 10%?

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: ?? on ??

=============================================================================================

Sample
Private key: 1000

Information you give me
If you give your private key 1000 public

1000-1 = 999 public key
1000 +1 = 1001 public key

1000 + 500 = 1500 public key
1000-500 = 500 public key
If I know the public key of 999,1001,1500,500
My information
Will it help me find my Bitcoin private key?

https://t.me/kyscolx

Of course. If you know this exact step between the known public key and target public key you will find the private for the target one. I mean if you know 1 and 500 in your example. But is these steps are just x and y - so no.
And also you should know the PRIVATE key from 1000+500, 1000-500, etc, not public one. Knowing just public is not enough because public key is just an ECDSA addition of 2 points.

dextronomous

full member

Activity: 431

Merit: 105

Happy New Year 2020 to all,

anything new under the sun regarding the project, maybe some gpu pollard.
or. Burt's Surprise

Sadlife

sr. member

Activity: 1400

Merit: 269

That is quite an interesting project im assuming this is still under development phase that's why, you're trying to find out the length and entropy of each BTC address are you trying to generate address as well so you check for duplicates ?
You could try this site https://www.blockcypher.com/dev/bitcoin/#documentation-structure this api has a lot of different functions including checking unconfirmed payments. You could try this out if you want more features to your project.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: bounty0z on November 27, 2019, 05:15:18 AM

+ How can I upload the tame and wild into my code, because when code start he create new empty file tame and wild ?

If you can specify what kind of code do you use, it will be easier to answer your question.
However as I remember there were 2 main pollard python codes in discussion - one used text files to store tame and wild, and another used memory to store them (without files).
So I can guess that you use the 1st one (with files).

In code you can find that in the beginning it creates (re-writes) tame and wild files. You need just comment or remove these rows from the code, like these:
#open("tame.txt",'w').close()
#open("wild.txt",'w').close()

'w' for only writing (an existing file with the same name will be erased)

Every time you run the code, it will use the same tame and wild tables, and will continue to search (however the start locations of kangaroos will be changed, but it is not so important - anyway kangaroos are jumping in random way)

bounty0z

member

Activity: 142

Merit: 70

Quote from: MrFreeDragon on November 26, 2019, 04:51:36 PM

Visually you also can imagine that all tame kangaroos are jumping with the cord - so you know the private key of every tame's location. But wild kangaroos are wild and you know only the jump step for them but do not know the private key for their location. Wild kangaroos are located just at another public point with uknown private key. As soon as wild and tame are met at the same point, you can calculate the unknown private key with the help of your "cord" connected with the tame kangaroo Wink

Thank you very much for explainning, but as you say now .. the wild and tame are good if we have lot of them "As soon as wild and tame are met at the same point" , so why not share all tame and wild founded and let pollard check them !?
+ How can I upload the tame and wild into my code, because when code start he create new empty file tame and wild ?

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: bounty0z on November 26, 2019, 12:03:51 PM

Hello,
any one here please can explain to me what mean by Wild and Tame ? , I know that they are hops of kangaroo, but how can I use them.
for example I want to know if i run pollard for #105 and get a Wild hop, but I shutdown the pollar code .. I don't want to start from the beginning so how can I import the Wild that I find in first ? ,and the same for Tame.

the second question is, what is tame and wild ? they are collision ? if yes and we can import them, so we can just everyone poste the wild and tame that he find and we will find it quicly !!

Thanks

In general, tame kangaroos are jumping "in the area" of private keys, and wild kangaroos are jumping "in the area" of public keys. If k is the private key, so public key for it will be Q = k*G, where G is basis point. Now, tame kangaroos are jumping in the area of private key (number), but wild kangaroos are jumping from the point Q (public key). There is a rule in ECDSA group addition: if we add some number to private key, the result will be the sum of the public keys, i.e. public key of the number (k + j) is (k+j) * G = k*G + j*G. So you can calculate the public of the jump step, add to public key of the private key to be found and receive the resulting point. The collision is the exact one point where tame and wild kangaroos are met.
In order to import all your jumps to continue, you should save the tables of their jumps (and later use them again).

Small example:
Imagine you want to find the private key for the public key Q 02ed3bace23c5e17652e174c835fb72bf53ee306b3406a26890221b4cef7500f88 [1]
This is the public key from the private number 100 (in hex 64), but you do not know this.

If tame kanagroo jumped to number tame_jump = 150 (in hex 96), we receive the public key from this number equal to 031f6014569d1203ae0c128ac00a41097609b16386bde7f857b908ea95e5eebbef [2]
And if wild kangaroo jumped by step wild_jump = 50, we should calculate the resulting point for wild as the addition of the known public key [1] and the public key of step 50 (in hex 32) which is 0229757774cc6f3be1d5f1774aefa8f02e50bc64404230e7a67e8fde79bd559a9a [3]

So, adding point [1] (Q) and point [3] (scalar addition in bitcoin ECDSA), we receive the resulting point 031f6014569d1203ae0c128ac00a41097609b16386bde7f857b908ea95e5eebbef [4]
No we see the collision: point [4] is exatcly the point [1].
Finally, while [4] equals to [2], the private key k is tame_jump - wild_jump = 150 - 50 = 100.
So, as wild and tame kangaroo jumped to the same point, we could find the private key as the difference between jumps.

Visually you also can imagine that all tame kangaroos are jumping with the cord - so you know the private key of every tame's location. But wild kangaroos are wild and you know only the jump step for them but do not know the private key for their location. Wild kangaroos are located just at another public point with uknown private key. As soon as wild and tame are met at the same point, you can calculate the unknown private key with the help of your "cord" connected with the tame kangaroo Wink

bounty0z

member

Activity: 142

Merit: 70

Hello,
any one here please can explain to me what mean by Wild and Tame ? , I know that they are hops of kangaroo, but how can I use them.
for example I want to know if i run pollard for #105 and get a Wild hop, but I shutdown the pollar code .. I don't want to start from the beginning so how can I import the Wild that I find in first ? ,and the same for Tame.

the second question is, what is tame and wild ? they are collision ? if yes and we can import them ,so we can just everyone poste the wild and tame that he find and we will find it quicly !!

Thanks

brainless

member

Activity: 348

Merit: 34

Hi all dev
seems you all only gone busy for your interest, its good, board in empty, no new updates, no new developmentsm, no new news, no sharing, etc
comunity wish you join back, and update, post your new work , idea's, etc

supika

newbie

Activity: 43

Merit: 0

Quote from: dextronomous on October 26, 2019, 06:56:43 PM

this thread not posting nada, niet, nothing,

23-10-2019 08:26:33 PMPosted by: brainless
but the posters are the best. serious hard work and nice work.
but no BurtW software as of yet released, just test result i guessed.

so guys let some of you be heard we wan't it to.

greetings.

Something new will appear in one month aprox, after they will find 110 puzzle.
After that they will need something new because kangaroo will not find 115 in a reasonable time.

dextronomous

full member

Activity: 431

Merit: 105

this thread not posting nada, niet, nothing,

23-10-2019 08:26:33 PMPosted by: brainless
but the posters are the best. serious hard work and nice work.
but no BurtW software as of yet released, just test result i guessed.

so guys let some of you be heard we wan't it to.

greetings.

brainless

member

Activity: 348

Merit: 34

Dear dev's
can you post script (python or c ) where multiple publickeys checking in kangroo bit range, (by reading pubkeys file i.e pubkeys.txt)
same as implemented in brainflayer, like bloomfilter check
bitcrack, vanitysearch, etc
yes its reduce speed but 10%, but if publickeys are in 100 or 200, it will not effect
love to see multiple pubkeys like bloom filter or else check in table, in bit range.
hope you could manage it too

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Did anybody make the analysis for the right DP_rarity? (in phyton code the "points" reconciliation is made only for X-coordinate multiple of DP_rariry: if P.x % DP_rarity == 0)

If we select very small DP_rarity, so many points will be saved, and wee need more memory/disk space. If we select very high DP_rarirty, so most of jump points will be missed, and the meeting point of wild and tame kagaroos could be missed as well.
What is the most effctive value of DP_rarity?

brainless

member

Activity: 348

Merit: 34

Seems no more new update in kangroo subject, all waiting GPu ver, but developer have it, and he maybe waiting to find 110 puzzle, but till no news in updates and upgrades in kaangroo
anyway any modification for multiple pubkey find in range space at once, by input file (multiple pubkey)
Huh

racminer

member

Activity: 245

Merit: 17

Quote from: PrivatePerson on October 10, 2019, 11:18:43 PM

Quote from: racminer on October 10, 2019, 06:07:35 AM

Even with higher speeds, runtime may fluctuate a lot. In order to compare performances, you need several trials.

Naturally I did a few measurements. Python scripts behaved the same way. The single-core and multi-core scripts showed approximately the same search time, although the multi-core speed was much higher.

In this case, remains the question whether the program stops running immediately or not when one of the threads finds the solution. We need to ask the developper Huh

PrivatePerson

member

Activity: 174

Merit: 12

Quote from: racminer on October 10, 2019, 06:07:35 AM

Even with higher speeds, runtime may fluctuate a lot. In order to compare performances, you need several trials.

Naturally I did a few measurements. Python scripts behaved the same way. The single-core and multi-core scripts showed approximately the same search time, although the multi-core speed was much higher.

st0ffl

newbie

Activity: 12

Merit: 0

Quote from: Telariust on October 08, 2019, 11:05:30 PM

Quote from: st0ffl

The idea is of course to only make sqr(2^(bit-2)) operations.

nice idea, i will add as option of boost in next release

Thank's Telariust!
It will take time but i could try to implement the kangaroo method myself in c#,
to learn if it would be possible to detect a parallelism for the average usage of sqr(2^(bit-2)) operations, when halfing x values of the searchspace,
unless you can confirm from your experience that there is no such behaviour detectable?

Currently it's just like you would guess in a keyspace of 1024 that the privatekey is greater than 512...
BUT...
If it is possible to find a privatekey less than 512 in less than 150% of sqr(2^(bit-1)) it should be an average overall speedgain.

My current idea to achieve that would be with the cost of an extra wild, when pushing the searchspace to point Infinity.
This wild point could just be the negation point of the orginal point without or with offset.
Cause i don't see ECPoint subtraction implemented in your script, you can use addition:
therefore the ECPoint offset calculation to wrap the space arround Infinity should be G.Multiply(ORDER-SpaceL-(SpaceL/2)).

Quote from: Telariust on October 08, 2019, 11:05:30 PM

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

Thank's

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: BurtW on October 10, 2019, 06:12:58 AM

BTW we keep all our points in memory in a hash table also. Disk access is a no no, especially when we are targeting a GPU (eventually).

Can you explain why don't you keep the points on disk, and keep them only in memory? And also please tell which point you keep - every point, or just some multipliers of predefined number (let's say 10^10)?

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: Telariust on October 08, 2019, 11:05:30 PM

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

BurtW, maybe I'm too active here, if you don’t like it, then you can ask me to leave and create a separate topic.

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

No problem. We enjoy your informative posts and have used several of your ideas in our program.

Right now I am very busy with work and my daughter is very busy in school so we have not had time to work on the program.

We will get back to our version when things slow down a bit.

BTW we keep all our points in memory in a hash table also. Disk access is a no no, especially when we are targeting a GPU (eventually).

racminer

member

Activity: 245

Merit: 17

Quote from: PrivatePerson on October 09, 2019, 11:26:40 PM

Quote from: racminer on October 09, 2019, 07:51:41 PM

why are you Huh

?

scaling depends on CPU, ie # of cores (typically 2,4,8 ... or 56 if you have a Intel® Xeon® Platinum 9282 Processor

)
and # of threads per core (which is one or two)

-t is generally equal to core number ... on some cpu's you might get better performance for -t equal to 2 x core number.

This is Ryzen 7 2700 (8 cores 16 threads)
I understand that -t is the number of threads.
The question is why the speed increases, but time does not decrease, more often it even increases.

Even with higher speeds, runtime may fluctuate a lot. In order to compare performances, you need several trials.

PrivatePerson

member

Activity: 174

Merit: 12

Quote from: racminer on October 09, 2019, 07:51:41 PM

why are you Huh

?

scaling depends on CPU, ie # of cores (typically 2,4,8 ... or 56 if you have a Intel® Xeon® Platinum 9282 Processor

)
and # of threads per core (which is one or two)

-t is generally equal to core number ... on some cpu's you might get better performance for -t equal to 2 x core number.

This is Ryzen 7 2700 (8 cores 16 threads)
I understand that -t is the number of threads.
The question is why the speed increases, but time does not decrease, more often it even increases.

racminer

member

Activity: 245

Merit: 17

Quote from: PrivatePerson on October 09, 2019, 04:48:02 AM

-t 4 -bits 55 1.0M j/s [runtime] 00:04:01

-t 16 -bits 55 3.2M j/s [runtime] 00:04:33 Huh

why are you Huh

?

scaling depends on CPU, ie # of cores (typically 2,4,8 ... or 56 if you have a Intel® Xeon® Platinum 9282 Processor

)
and # of threads per core (which is one or two)

-t is generally equal to core number ... on some cpu's you might get better performance for -t equal to 2 x core number.

racminer

member

Activity: 245

Merit: 17

Quote from: Telariust on October 08, 2019, 11:05:30 PM

Quote from: racminer

..where exactly do you store the tame and wild kangaroos as it is done in the "tame.txt" and "wild.txt" files for the python code..

in hashtable
ok, i will add output to file distinguished points in next release

Thanks for your answer and all your answers.
The Hash table is only 1024 entries, is it enough for cases like #110 ?

PrivatePerson

member

Activity: 174

Merit: 12

-t 4 -bits 55 1.0M j/s [runtime] 00:04:01

-t 16 -bits 55 3.2M j/s [runtime] 00:04:33 Huh

Code:

PS D:\btc\vs-kangaroo-0.01> ./vs-kangaroo_0.01.exe -v 1 -t 4 -bits 55
[###########################################################]
[# Pollard-kangaroo PrivKey Recovery Tool #]
[# (based on engine of VanitySearch 1.15) #]
[# bitcoin ecdsa secp256k1 #]
[# ver0.01 #]
[###########################################################]
[DATE(utc)] 09 Oct 2019 09:20:10
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pow2bits] 55
[rangeW] 2^54..2^55 ; W = U - L = 2^54
[DPsize] 1024 (hashtable size)
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pubkey#55] loaded
[Xcoordinate] 85A30D8413AF4F8F9E6312400F2D194FE14F02E719B24C3F83BF1FD233A8F963
[Ycoordinate] 0EB400323654CEC63999B56F4BA44E8B21AB92D9D697FABE4666DF3678585669
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] Sp-table of pow2 points - ready
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] recalc Sp-table of multiply UV
[UV] U*V=1*3=3 (0x03)
[optimal_mean_jumpsize] 134217728
[meanjumpsize#30] 107374182(now) <= 134217728(optimal) <= 207820998(next)
[i] Sp[30]|----------------J-------------------------------------------|Sp[31]
[i] this Sp set has low efficiency (over -25%) for this mean jumpsize
[JmaxofSp] Sp[30]=107374182 nearer to optimal mean jumpsize of Sp set
[DPmodule] 2^25 = 33554432 (0x0000000002000000)
[+] 1T+3W kangaroos - ready
[CPU] threads: 4
[th][tame#1] run..
[th][wild#1] run..
[th][wild#2] run..
[th][wild#3] run..
[-][ 00:04:00 ; 1.0M j/s; 249.0Mj 92.8%; dp/kgr=1.5; 00:00:18 ]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[prvkey#55] 0x000000000000000000000000000000000000000000000000006ABE1F9B67E114
[i] 1.0M j/s; 250.0Mj of 268.0Mj 93.4%; DP 1T+3W=2+2=4; dp/kgr=2.0;
[runtime] 00:04:01
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[DATE(utc)] 09 Oct 2019 09:24:12
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[x] EXIT

Code:

PS D:\btc\vs-kangaroo-0.01> ./vs-kangaroo_0.01.exe -v 1 -t 16 -bits 55
[###########################################################]
[# Pollard-kangaroo PrivKey Recovery Tool #]
[# (based on engine of VanitySearch 1.15) #]
[# bitcoin ecdsa secp256k1 #]
[# ver0.01 #]
[###########################################################]
[DATE(utc)] 09 Oct 2019 09:36:15
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pow2bits] 55
[rangeW] 2^54..2^55 ; W = U - L = 2^54
[DPsize] 1024 (hashtable size)
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pubkey#55] loaded
[Xcoordinate] 85A30D8413AF4F8F9E6312400F2D194FE14F02E719B24C3F83BF1FD233A8F963
[Ycoordinate] 0EB400323654CEC63999B56F4BA44E8B21AB92D9D697FABE4666DF3678585669
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] Sp-table of pow2 points - ready
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] recalc Sp-table of multiply UV
[UV] U*V=7*9=63 (0x3f)
[optimal_mean_jumpsize] 536870912
[meanjumpsize#28] 603979773(now) <= 536870912(optimal) <= 1166305772(next)
[i] Sp[27]|----------------------------------------------J-------------|Sp[28]
[i] this Sp set has low efficiency (over -25%) for this mean jumpsize
[JmaxofSp] Sp[28]=313174696 nearer to optimal mean jumpsize of Sp set
[DPmodule] 2^25 = 33554432 (0x0000000002000000)
[+] 7T+9W kangaroos - ready
[CPU] threads: 16
[th][tame#1] run..
[th][wild#1] run..
[th][tame#3] run..
[th][tame#4] run..
[th][tame#5] run..
[th][tame#6] run..
[th][tame#7] run..
[th][tame#2] run..
[th][wild#2] run..
[th][wild#3] run..
[th][wild#4] run..
[th][wild#5] run..
[th][wild#6] run..
[th][wild#7] run..
[th][wild#9] run..
[th][wild#8] run..
[|][ 00:03:57 ; 3.2M j/s; 770.0Mj 287.1%; dp/kgr=13.5; 00:00:00 ]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[prvkey#55] 0x000000000000000000000000000000000000000000000000006ABE1F9B67E114
[i] 2.8M j/s; 776.0Mj of 268.0Mj 289.0%; DP 7T+9W=13+14=27; dp/kgr=13.5;
[runtime] 00:04:33
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[DATE(utc)] 09 Oct 2019 09:40:49
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[x] EXIT

croxNN

newbie

Activity: 13

Merit: 3

Telariust, there is nothing in Source Code, only README.md

Telariust

jr. member

Activity: 38

Merit: 18

Quote from: PrivatePerson on October 09, 2019, 11:26:40 PM

I understand that -t is the number of threads.
The question is why the speed increases, but time does not decrease, more often it even increases.

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)

Code:

C:\Users\User\source\repos\VanitySearch-1.15_kangaroo\x64\Rel_SM52>vs-kangaroo -v 1 -t 4 -bits 42
[###########################################################]
[# Pollard-kangaroo PrivKey Recovery Tool #]
[# (based on engine of VanitySearch 1.15) #]
[# bitcoin ecdsa secp256k1 #]
[# ver0.01 #]
[###########################################################]
[DATE(utc)] 08 Oct 2019 23:07:47
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pow2bits] 42
[rangeW] 2^41..2^42 ; W = U - L = 2^41
[DPsize] 1024 (hashtable size)
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pubkey#42] loaded
[Xcoordinate] EEC88385BE9DA803A0D6579798D977A5D0C7F80917DAB49CB73C9E3927142CB6
[Ycoordinate] 28AFEA598588EA50A6B11E552F8574E0B93ABD5595F5AA17EA3BE5304103D255
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] Sp-table of pow2 points - ready
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] recalc Sp-table of multiply UV
[UV] U*V=1*3=3 (0x03)
[optimal_mean_jumpsize] 2097152
[meanjumpsize#24] 2097151(now) <= 2097152(optimal) <= 4026531(next)
[i] Sp[24]|J------------------------------------------------------------|Sp[25]
[JmaxofSp] Sp[24]=2097151 nearer to optimal mean jumpsize of Sp set
[DPmodule] 2^18 = 262144 (0x0000000000040000)
[+] 1T+3W kangaroos - ready
[CPU] threads: 4
[th][tame#1] run..
[th][wild#1] run..
[th][wild#2] run..
[th][wild#3] run..
[|][ 00:00:04 ; 1.1M j/s; 4.0Mj 107.4%; dp/kgr=10.0; 00:00:00 ]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[prvkey#42] 0x000000000000000000000000000000000000000000000000000002A221C58D8F
[i] 1.0M j/s; 5.0Mj of 4.0Mj 123.6%; DP 1T+3W=8+14=22; dp/kgr=11.0;
[runtime] 00:00:05
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[DATE(utc)] 08 Oct 2019 23:07:53
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[x] EXIT

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

Quote from: j2002ba2 on July 11, 2019, 07:14:49 AM

BitCrack runs at about 715 MKeys/s on Tesla V100 - look here.
If we remove hash160, the rate would be 1430 Mj/s. Mj here stands for million kangaroo jumps.

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

Quote from: j2002ba2 on July 12, 2019, 05:53:45 AM

https://imgur.com/a/f3zTmTa

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

now unclear..

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

https://bitcointalksearch.org/topic/m.48224432
November 25, 2018 this man speaks as if he already has a finished implementation.

Quote from: j2002ba2 on July 12, 2019, 05:53:45 AM

https://imgur.com/a/f3zTmTa

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

st0ffl

newbie

Activity: 12

Merit: 0

Quote from: brainless on October 07, 2019, 01:39:56 PM

hi
in script, there is bug, or maybe he unable to catch point, as
if you have 37 bit pubkey
and you command is
./script 40 02xxxxxxpublickey
40 bit mean search in bit range
but script will find key in 37 bit
if you have 42 bit key, and same command for search in 40 bit by apply 40 or 8:fffff.... bit range, script will find 42 key

its not restrict only for define bit range
mean always find start from 8 to onword, so its take time consume, Smiley
test it

Yes, this was my point.
I first thought that there is a parallel behaviour, cause the script was finding the publickey when changing y value only, and we could use it to only make sqr(2^(bit-2)) operations,
unitil i found a completely different pubkey from another space.
You don't have to set from 8:... bitspace it also works with orginal keyspace

It's not a bug i guess...i am cleary not an expert in this matter Tongue

, but that's what i think:
It seems logical, it will just take longer on average to find the key.
The average jumpsize should be calculated from the searchspace.
When you search for exampe puplic key from 37 bit within 40 bit the average jumpsize should be bigger and the opposite when searching 43bit pubkey within 40 bit.

It's strange, that when you change only the y value of the key, you will find the orginal publickey with privatekey, but not the one you changed.

brainless

member

Activity: 348

Merit: 34

hi
in script, there is bug, or maybe he unable to catch point, as
if you have 37 bit pubkey
and you command is
./script 40 02xxxxxxpublickey
40 bit mean search in bit range
but script will find key in 37 bit
if you have 42 bit key, and same command for search in 40 bit by apply 40 or 8:fffff.... bit range, script will find 42 key

its not restrict only for define bit range
mean always find start from 8 to onword, so its take time consume, Smiley
test it

st0ffl

newbie

Activity: 12

Merit: 0

Quote from: brainless on October 03, 2019, 01:25:26 AM

i sent you PM, 2 time in last 2 days, have some time for reply
Looking Farword

seems like you need to change your settings too

brainless

member

Activity: 348

Merit: 34

Quote from: st0ffl on October 02, 2019, 07:06:15 PM

I deleted my posts to avoid any confusions.

Now i better understand how kangaroo jumping works, i didn't even know that it is possible to find a publickey which is not in the space we are searching for.
That's why it finds the publickey when you just change Y.
I thought that when a tame kangaroo jumps out of space, a new tame and wild kangaroo would be set within the space to start jumping again.

As my suggestion, it would be the same if you just set the searchspace for from 2^(bit-1) > (2(bit)-1) to (2^(bit-1) + 2^(bit-2)) > (2(bit)-1).
You would have a 50% chance to find the key in sqr(2^(bit-2)).
In my tests it must have been luck to find the keys not in that 50%chance in less time than average.
The only benefit i see by pushing the space with the middle to Infinity point, would be if a X value match could be detected when a wildkangaroo starts in negative mirrored space. That would possible be a rarely case by the time it catches up to the positive space where all tame kangaroos would start.

i sent you PM, 2 time in last 2 days, have some time for reply
Looking Farword

st0ffl

newbie

Activity: 12

Merit: 0

I deleted my posts to avoid any confusions.

Now i better understand how kangaroo jumping works, i didn't even know that it is possible to find a publickey which is not in the space we are searching for.
That's why it finds the publickey when you just change Y.
I thought that when a tame kangaroo jumps out of space, a new tame and wild kangaroo would be set within the space to start jumping again.

As my suggestion, it would be the same if you just set the searchspace for from 2^(bit-1) > (2^(bit)-1) to (2^(bit-1) + 2^(bit-2)) > (2(bit)-1).
You would have a 50% chance to find the key in sqr(2^(bit-2)).
In my tests it must have been luck to find the keys not in that 50%chance in less time than average.
The only benefit i see by pushing the space with the middle to Infinity point, would be if a X value match could be detected when a wildkangaroo starts in negative mirrored space. That would possible be a rarely case by the time it catches up to the positive space where all tame kangaroos would start.

st0ffl

newbie

Activity: 12

Merit: 0

Quote from: racminer on October 01, 2019, 07:34:20 PM

Quote from: st0ffl on October 01, 2019, 04:52:11 PM

Here is another example of #40

#40 sqr(2^(bit-1))
python pollard-kangaroo-multi.py 40
//privkey = 1003651412950

#40 sqr(2^(bit-2))
python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399
//privkey = 179017692118

Addfactor: 824633720832
//result1 = 1003651412950 true

824633720832 is just 0xC000000000
179017692118 is 0x29AE4933D6
1003651412950 is 0xE9AE4933D6

So 0xC000000000 is just the mid point of the normal #40 range 8000000000:FFFFFFFFFF
in other words the #40 sqr(2^(bit-2)) range you are mentioning is just the position of the private key from the mid-point.
You are not doing less work, you've just changed the origin.
Instead of working with the tame kangaroo matching the private key solution, you are working with the corresponding wild kangaroo.

Exactly that was the plan > wraping the space W with the middle of the space to point infinity.
So that actually all x values get halfed.
I thought possibly that when a wild kangaroo jumps, a jump from the tame kangaroo in the negative space in the different direction could also lead to the same result in less time(cause it would be the same distance).
The key is definitely to find in the space(bit-2), however if you say regarding the kangaroo method, that there is no speed gain, the method is useless.
i have to test #35. i would not understand if the key is not findable. like #50 if the key is on the negative side it will find the privatekey and publickey on the positiv side,there will be just no publickey match> Watch it in the console im not sure if gets to the result.txt
Thanks for testing!

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: racminer on October 01, 2019, 07:34:20 PM

Quote from: st0ffl on October 01, 2019, 04:52:11 PM

Here is another example of #40

#40 sqr(2^(bit-1))
python pollard-kangaroo-multi.py 40
//privkey = 1003651412950

#40 sqr(2^(bit-2))
python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399
//privkey = 179017692118

Addfactor: 824633720832
//result1 = 1003651412950 true

824633720832 is just 0xC000000000
179017692118 is 0x29AE4933D6
1003651412950 is 0xE9AE4933D6

So 0xC000000000 is just the mid point of the normal #40 range 8000000000:FFFFFFFFFF
in other words the #40 sqr(2^(bit-2)) range you are mentioning is just the position of the private key from the mid-point.
You are not doing less work, you've just changed the origin.
Instead of working with the tame kangaroo matching the private key solution, you are working with the corresponding wild kangaroo.

Absolutely!

In general terms, it could be explaind like this: for bit key the range is from 2^(bit-1) up to 2^(bit)-1, where the total number of combinations (range length) is 2^(bit-1).
2^(bit-2) is a half of 2^(bit-1), so 2^(bit-1) + 2^(bit-2) is 1.5 * 2^(bit-1) --> the absolute middle of the total range for the (bit) key.

racminer

member

Activity: 245

Merit: 17

Quote from: st0ffl on October 01, 2019, 04:52:11 PM

Here is another example of #40

#40 sqr(2^(bit-1))
python pollard-kangaroo-multi.py 40
//privkey = 1003651412950

#40 sqr(2^(bit-2))
python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399
//privkey = 179017692118

Addfactor: 824633720832
//result1 = 1003651412950 true

824633720832 is just 0xC000000000
179017692118 is 0x29AE4933D6
1003651412950 is 0xE9AE4933D6

So 0xC000000000 is just the mid point of the normal #40 range 8000000000:FFFFFFFFFF
in other words the #40 sqr(2^(bit-2)) range you are mentioning is just the position of the private key from the mid-point.
You are not doing less work, you've just changed the origin.
Instead of working with the tame kangaroo matching the private key solution, you are working with the corresponding wild kangaroo.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: st0ffl on October 01, 2019, 04:52:11 PM

Here is another example of #40

#40 sqr(2^(bit-1))
python pollard-kangaroo-multi.py 40
//privkey = 1003651412950

#40 sqr(2^(bit-2))
python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399
//privkey = 179017692118

Addfactor: 824633720832
//result1 = 1003651412950 true

This method is not universal. It depends on the 2nd bit actually Cool

So, for #40 it works. But for #35 for example it will not work. For #50 it will not work as well.

First bit is always 1 in these transaction chalange keys. But the 2nd bit could be 1 or 0 (as any other bit). You decrease the bit power considering that the 2nd bit is 1, but it is not obligitary. It also could be 0.

racminer

member

Activity: 245

Merit: 17

Quote from: Telariust on September 16, 2019, 01:58:06 PM

-----------------------------------------------------------------

@Telariust
Very nice work. I've tried your C code and it hops two times faster than 57fe python code.
I can't figure out where exactly do you store the tame and wild kangaroos as it is done in the "tame.txt" and "wild.txt" files for the python code.

thanks for your help

st0ffl

newbie

Activity: 12

Merit: 0

Here is another example of #40

#40 sqr(2^(bit-1))
python pollard-kangaroo-multi.py 40
//privkey = 1003651412950

#40 sqr(2^(bit-2))
python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399
//privkey = 179017692118

Addfactor: 824633720832
//result1 = 1003651412950 true

st0ffl

newbie

Activity: 12

Merit: 0

Quote from: ?? on ??

sending you PM, your need allow my id for send PM to you

i changed the settings to allow newbie messages

st0ffl

newbie

Activity: 12

Merit: 0

Quote from: ?? on ??

need detail explain for this area
example to test:

from
#50 = 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6

to

0-48 02bc9d041a4839d3bef61e319cd02d3b177292ccb79ed27c1bf6043ab0ec635bfd

steps guide

1. Create ECPoint "p" from 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
2. Calculate subtraction space "sub"= (2^(bit-1)) + (2^(bit-2));
3. Create ECPoint from sub "subP" = G.Multiply(sub);
4. Create ECPoint new "newP" = p.Subtract(subP);
5. Create compressed publicKey string "newPK" = newP.GetEncoded(True).ToString();
6. Calculate your "newkeySpaceU" value = (2^(bit-2))-1
7. Convert newkeySpaceU from decimal to hexadecimal string= newKeySpace.ToString("X");
8. Use pollard-kangaroo-multi.py 8:newkeySpaceU newPubkey
(Correctly keySpace L should be always 0, by default 8 is minimum)
9. Convert your result prvkey output from hexadecimal to BigInteger "res"
10.Calculate "offset1" = res + sub and calculate "offset2" = ((Order -res) + sub)%Order
11. Generate new ECPOINT "offset1P" and "offset2P" = G.Multiply(offset1) and G.Multiply(offset2)
12. Compare "offset1P" to "p" = if(p.Equals(offset1P)) offset1 is my prvkey; else offset2 is my privkey

st0ffl

newbie

Activity: 12

Merit: 0

Quote from: MrFreeDragon on October 01, 2019, 06:01:05 AM

Can you please clarify there is the benefit in your method? You are saying that "Now we only have to check the x values from space 0 to 2^(bit-2)", so we need to check 2^(bit-2) combinations. It is just 2 times less that the brutforce of the full range. Not effective.
However in Pollard method we should make only sqr (2^(bit-1)) operations, which is much much less than in your method.

Example: for 110 bit key, you suggest to check 2^108 combinations, but in Pollard method we need only 2^54.5 operations.
So why is your method valuable? What is the main idea and advantage?

The idea is of course to only make sqr(2^(bit-2)) operations.

for #50:

python pollard-kangaroo-multi.py 50 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6

should be equivalent to

python pollard-kangaroo-multi.py 8:FFFFFFFFFFFF 02bc9d041a4839d3bef61e319cd02d3b177292ccb79ed27c1bf6043ab0ec635bfd

(8 is by default minimum bit using pollard-kangaroo-multi.py)

edit: sorry was the wrong pubkey for #50 in first place

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: ?? on ??

In the case of the puzzle transactions a publickey should be in the space 2^(bit-1) to (2^bit)-1,
we can just calculate 2^(bit-1) + 2^(bit-2) as a point and subtract it from our known publickey.
Our new generated public key will be within the space(ORDER - 2^(bit-2)) to 2 ^(bit-2).
Now we only have to check the x values from space 0 to 2^(bit-2).
When we find the solution to the calculated publickey, the solution to our orginal publickey will be either solution or (ORDER - solution) + subtraction factor.

Can you please clarify there is the benefit in your method? You are saying that "Now we only have to check the x values from space 0 to 2^(bit-2)", so we need to check 2^(bit-2) combinations. It is just 2 times less that the brutforce of the full range. Not effective.
However in Pollard method we should make only sqr (2^(bit-1)) operations, which is much much less than in your method.

Example: for 110 bit key, you suggest to check 2^108 combinations, but in Pollard method we need only 2^54.5 operations.
So why is your method valuable? What is the main idea and advantage?

usama12

newbie

Activity: 9

Merit: 0

Hi BurtW I have gone through whole thread and its very interesting and informative. I am interested to get listed on your list of testers.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: ?? on ??

What I'm trying to figure out is, how to express this point addition/multiplication in algebraic terms.

did you look at the pictures in that article with the curves and the lines? if you haven't first do that and then come back and read on. mainly this:

the point addition is basically defined as drawing a line between the two points, finding the third point (there is always a third point "intersection" when the other 2 points are on the curve) on the curve and negating that.

we call the point without a name S on this picture, and first have to find S then find R from that.
first a line between the two points and find the "formula" for that line. since the line is straight the formula is y = mx + a where m is the slope also known as λ.
λ = (y_q-y_p)/(x_q-x_p) and
y = y_p + λ(x-x_p) is that formula using point P (we can use any of the other 3 points too). if we put it in the elliptic curve formula (y² = x³ + ax + b) we get:
x³ − λ²x² + a+2λ²x_p −2λy_px + (b−(λx_p−y_p)²) = 0
we know thanks to Vieta that in a quadratic equation ax³ + bx² + cx + d =0 that the sum of roots r₁, r₂ and r₃ is equal to -b/a so in our case sum of three values for x which are the coordinates of the 3 points on the straight line is equal to -(-λ²/1)= λ²
hence we can calculate the x coordinate of point S:
x_p+x_q+x_s=λ² => x_s=λ²−x_p−x_q. and since x_s=x_r we have found the x coordinate of our point R which is here: https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication#Point_addition
to find its y coordinate of S we simply use the line's formula and since y_r=-y_s we just have to flip the sign hence the y_r formula in wikipedia link

2 additional things to note:
1. point doubling aka adding a point to itself is the same math with only one difference: x and y coordinate of P and Q are the same.
2. all the math here is modular (mod curve's prime)

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ZafotheNinja on September 24, 2019, 10:12:34 PM

This seems like a noobish question but, with the secp256k1 curve, what is the formula for calculating the Galois field?

The bitcoin wiki gives the parameters for the curve, but I haven't been able to find a formula for how the parameters interact.

Any extra reading materials would also be helpful.

Not sure exactly what you are asking here. First of all the points on the elliptical curve for a group, not a field.

Here is a pretty good primer on the defined addition operation for the group.

https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3

ZafotheNinja

jr. member

Activity: 30

Merit: 1

This seems like a noobish question but, with the scp256k1 curve, what is the formula for calculating the Galois field?

The bitcoin wiki gives the paramaters for the curve, but I haven't been able to find a formula for how the parameters interact.

Any extra reading materials would also be helpful.

racminer

member

Activity: 245

Merit: 17

#105 found !

dextronomous

full member

Activity: 431

Merit: 105

Hey guys, especially Telariust, Racminer, BurtW,
really impressed by you'r calculation skills, math skills.
Who's going to release the exe file first, reading he want's to wait you'r
release first, then again, could you guys ellaborate a bit on when this might or will happen
thanks in advance, will be waiting for the software.

What to do in the meantime, can't do nothing then.
Learn some python then.

Huh

just almost forgetting another question, when is the tested gpu version there for us readers to review.
cheers

racminer

member

Activity: 245

Merit: 17

Quote from: ?? on ??

I mentioned that there is no need to compare T and W lists at every hop because comparing lists is time consuming.
You may insert an if ( hops % cycle ==0) { compare ...} where cycle can be 100 000 or even 1 000 000 especially for higher cases.
for example, case 56 , you have 957 628 504 hops and 885 620 875 compares, take cycle=1 000 000, I am pretty sure
that timing will be down to 15 min.
In other words, you don't need to check for collisions at every hop Roll Eyes

Three points:

1) Our code is very different from the published python code with many modification for speed and to get it ready to move to a GPU. We do not do list comparisons like the python code does.

2) The number we are displaying is the actual total number of point to point comparisons and is not the same as the number of list comparisons in the python code.

3) To get an equivalent number from the python code that uses the list compare function you would have to count up the actual number of point to point comparisons that are hidden down in the list comparison function.

OK
1) Our code is very different from the published python code with many modification for speed and to get it ready to move to a GPU. We do not do list comparisons like the python code does.
>>> Pollard-kangaroo is Pollard-kangaroo as far as I know

2) The number we are displaying is the actual total number of point to point comparisons and is not the same as the number of list comparisons in the python code.
>>> up to case 63, the lists are quite small in size (rarely more than 200), so brute force point to point is around 200x200 = 40000 still small.

3) To get an equivalent number from the python code that uses the list compare function you would have to count up the actual number of point to point comparisons that are hidden down in the list comparison function.
>>> I did count, the number of hops is around 20 times bigger that point to point comparison in case 63.

But why is yours so slow as compared to the simple python code ?

Code:

Case #     time (sec)
50    148.46
51    120.88
52    189.33
53    204.99
54    674.51
55    441.58
56    945.33
57   1509.22
58   2685.02
59   2300.80
60   4389.98
61   2958.66
62   7802.91
63  10239.27

whatever your code is (which we have not seen as yet

), basically at some point you are comparing, all what I'm suggesting to you is to try defer comparing as much as possible.

Thanks.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

We have a new record for our little program: 57 bit private key in 1.73 hours averaging 153,791 hops per second using only 310,784 bytes of dynamically allocated memory. We still have not yet implemented all of the great ideas in this thread that will improve the hop rate and implementation/algorithm.

Code:

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 56
seed  = none (default value)
b     = 2 ^ 57 = 0x0200000000000000
a     = 2 ^ 56 = 0x0100000000000000
P     = 0x02A521A07E98F78B03FC1E039BC3A51408CD73119B5EB116E583FE57DC8DB07AEA (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x01EB25C90795D61C
s*G   = 0x02A521A07E98F78B03FC1E039BC3A51408CD73119B5EB116E583FE57DC8DB07AEA (33 bytes)
numt  = 0x8 (8)
mem   = 0x4BE00 (310784) bytes
cmps  = 0x34C9808B (885620875)
hops  = 0x39144058 (957628504)
hps   = 153790.653757
time  =    1.7297 hours (6226831609100 nsecs)

Quote from: Telariust on September 16, 2019, 01:58:06 PM

so as not to create possible problems for you, I will publish the source code only after you.
At this time, I will try to write addition in affine coordinates, which is the fastest way, +30% expected speed-up.

We are doing this to learn. It would be no problem for us if you publish your source code. We already have the published python source code and have looked at it in order to improve our program. You do not need to wait for us to publish. The science fair is not until next year so we have a lot of time to get everything just right and then move the code on to a GPU.

Statistics from our most recent run:

Code:

test       time         hps       hops       compares    mem(bytes)    total time
----  --------------  -------  ----------  ------------  ----------  --------------
   0    0.8564 msecs     1167  1           3             1232        856400
   1    0.7479 msecs     1337  1           3             1232        747900
   2    0.6127 msecs     1632  1           3             1232        612700
   3    8.6445 msecs      925  8           10            1232        8644500
   4    1.6279 msecs     6757  11          13            1232        1627900
   5    1.9472 msecs     7703  15          17            1232        1947200
   6   12.3022 msecs     4226  52          54            1232        12302200
   7    2.0009 msecs    15992  32          34            1232        2000900
   8    3.2746 msecs    13742  45          47            1232        3274600
   9   10.7214 msecs    47568  510         512           1232        10721400
  10   18.3054 msecs    48783  893         895           1232        18305400
  11   26.3645 msecs    53594  1413        1415          1232        26364500
  12   78.4207 msecs    37949  2976        2978          1232        78420700

  13   13.5507 msecs    61841  838         338           21888       13550700
  14   15.4483 msecs    45441  702         38            23360       15448300
  15   22.4275 msecs    48378  1085        143           26304       22427500
  16   25.1679 msecs    36355  915         305           32192       25167900
  17   31.0598 msecs    24050  747         141           43968       31059800
  18   44.3618 msecs    60975  2705        2132          67520       44361800
  19   63.4771 msecs    23866  1515        949           114624      63477100
  20  120.1801 msecs    32010  3847        3128          208832      120180100
  21  200.2294 msecs    26854  5377        5145          397248      200229400
  22  397.8554 msecs    30810  12258       11740         774080      397855400

  23   91.7390 msecs    97635  8957        5788          40896       91739000
  24   64.6165 msecs    60897  3935        770           42368       64616500
  25  130.9894 msecs   108573  14222       10071         45312       130989400
  26  105.1900 msecs    92489  9729        6966          51200       105190000
  27  152.1824 msecs   115979  17650       13956         62976       152182400
  28  103.3762 msecs    76613  7920        4563          86528       103376200
  29    1.3121 secs    190967  250564      245502        133632      1312076400
  30  860.7668 msecs   175329  150918      146792        227840      860766800
  31    6.7634 secs    194092  1312726     1302011       416256      6763397900
  32    8.2153 secs    195437  1605582     1592230       793088      8215338900

  33    2.5348 secs    136228  345314      276375        78336       2534806300
  34    1.2517 secs     62445  78166       8225          79808       1251746900
  35    4.6382 secs    163879  760109      689150        82752       4638222000
  36   38.0879 secs    187772  7151877     6987945       89152       38087934000
  37   18.5839 secs    182235  3386646     3302690       100416      18583879400
  38   25.5975 secs    183080  4686411     4596034       123968      25597487500
  39   46.6920 secs    160988  7516894     8474293       171072      46691996800
  40    1.7609 secs     95305  167826      98613         265280      1760925900
  41    3.6092 mins    163432  35391791    40060843      453696      216552401100
  42   23.0696 mins    181027  250574243   249647494     830528      1384178187200

  43   58.8688 secs    113200  6663978     4542748       152544      58868821100
  44    1.8608 mins    148273  16554034    14381807      154016      111645595700
  45    2.2344 mins    154316  20688475    18479327      156960      134065352000
  46   46.5020 secs     83000  3859681     1996004       162848      46501976100
  47   48.5642 mins    176154  513288902   505356026     175136      2913854013900
  48   17.2490 mins    174174  180259712   176439508     198176      1034938770000
  49   23.4304 mins    175194  246292149   242207587     245280      1405822811400
  50   18.4636 mins    151963  168347310   188535204     339488      1107817430400
  51   58.0994 mins    153719  535862165   606643869     527904      3485962802800
  52   34.3880 mins    153038  315762297   357149197     904736      2063282714200

  53   40.2602 mins    120565  291240607   223324940     300480      2415611495500
  54   41.4377 mins    121698  302574766   234686603     301952      2486260671300
  55   54.7941 mins    135532  445582526   376662553     304896      3287646391600
  56    1.7297 hours   153790  957628504   885620875     310784      6226831609100

brainless

member

Activity: 348

Merit: 34

Quote from: ?? on ??

Telariust,

Could you do us a favor and run our version of the secp256k1_ecmult_gen function through your same benchmarks and let us know what you get? This way we can compare apples to apples on hop rates.

Code:

static inline void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *gn)
{
    /* Computing (n+b)G - bG instead of nG directly, no gain by changing this. */
    secp256k1_scalar gnb;
    secp256k1_scalar_add(&gnb, gn, &ctx->blind);
    *r = ctx->initial;

    for (int j = 0; j < 64; j++) {
        secp256k1_ge add;
        const int bits = secp256k1_scalar_get_bits(&gnb, j * 4, 4);
        secp256k1_ge_from_storage(&add, &(*ctx->prec)[j][bits]);
        secp256k1_gej_add_ge_var(r, r, &add, NULL);
    }
}

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

Code:

for(uint64_t i = 1; i<1000000 ; ++i){
	secp256k1_scalar_set_uint64(&scalarK, TestGej.x.n[0]); // pseudo random points
	MULT_FUNCTION_HERE(&context, point_jacobian, &scalarK)
}

origin secp256k1_ecmult_gen()
1M at 26sec 699msec; 0.037 Mk/s

custom BurtW secp256k1_ecmult_gen()
1M at 22sec 498msec; 0.044 Mk/s

my processor 13-6100 ddr4 8gb
tel-kangro-0.83
speed
[~] 384.0K j/s; 14.1Mj 0.0%; dp/kgr=0.0; [ 0d 00:00:36s lost_TIME_left 750y 6m 8d 07:20:44s ]

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Thanks for all of your help! We have been very carefully implementing all the best suggestions. The latest test results using my laptop computer are as follows.

Average h/s over all runs from test 0 through test 49: 80,028

Max h/s reached was: 194,547

We have updated the run results in the OP.

Code:

test     hps
----   ------- 
   0     2,420
   1     1,211
   2     2,197
   3    13,367
   4    11,451
   5     9,942
   6    23,740
   7    18,849
   8    22,703
   9    48,497
  10    49,485
  11    51,391
  12    55,693
  13    66,687
  14    44,872
  15    50,782
  16    44,037
  17    31,128
  18    62,800
  19    24,245
  20    27,484
  21    27,204
  22    30,454
  23    97,422
  24    62,548
  25    97,612
  26    90,048
  27   110,399
  28    63,970
  29   163,713
  30   147,993
  31   194,547
  32   167,280
  33   132,836
  34    58,530
  35   163,698
  36   173,776
  37   128,880
  38   138,391
  39   121,995
  40    83,115
  41   140,884
  42   123,750
  43    95,156
  44   105,499
  45   121,877
  46    79,010
  47   139,557
  48   138,639
  49   139,645

Telariust

jr. member

Activity: 38

Merit: 18

Quote from: Telariust

it very slow for 1core C/C++ openssl/secp256k1, it should be more!

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

Code:

C:\cygwin64\home\User\pollard-kangaroo>pollard-kangaroo.exe

[###########################################################]
[#          Pollard-kangaroo PrivKey Recovery Tool         #]
[#            C99, bitcoin-core/secp256k1 library          #]
[#                        singlecore                       #]
[#                          ver 0.1                        #]
[###########################################################]
[DATE(utc)] 16 Sep 2019 18:23:53
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pow2bits] 2^40
[range] 2^39..2^40 ; W = U - L = 0x0000008000000000 (2^39)
[maxDP] 1024 (max elements in hashtable)
[DPmodule] 0x0000000000040000
[pow2Jmax] 23
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
 --> TEST MODE
[pubkey(tests)] 03A2EFA402FD5268400C77C20E574BA86409EDEDEE7C4020E4B9F0EDBEE53DE0D4
 --> pubkey valid!
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] Sp-table of pow2 points - ready
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] T1+W1 herds - ready
 --> [0y 0m 0d 00:00:06s] [0.23Mk/s] [0y 0m 0d 00:00:11s]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[i] 1700051j; DP T+W=4+3=7; dp/kgr=3.5;
[prvkey#40] 000000000000000000000000000000000000000000000000000000E9AE4933D6
[#############################; passtime: 0y 0m 0d 00:00:06s]
[####################################; precision:   6s  38ms]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[DATE(utc)] 16 Sep 2019 18:23:59
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[x] EXIT

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

Code:

 --> [0y 0m 0d 00:00:16s] [0.09Mk/s] [0y 0m 0d 00:00:27s]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[i] 1700051j; DP T+W=4+3=7; dp/kgr=3.5;
[prvkey#40] 000000000000000000000000000000000000000000000000000000E9AE4933D6
[####################################; precision:  17s  18ms]

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

Code:

 --> [0y 0m 0d 00:00:48s] [0.03Mk/s] [0y 0m 0d 00:01:19s]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[i] 1700051j; DP T+W=4+3=7; dp/kgr=3.5;
[prvkey#40] 000000000000000000000000000000000000000000000000000000E9AE4933D6
[####################################; precision:  51s 595ms]

40bits, w=39bit, 2w^(1/2) at 127sec

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

Quote from: BurtW

Quote from: Telariust

so as not to create possible problems for you, I will publish the source code only after you.

We are doing this to learn. It would be no problem for us if you publish your source code. We already have the published python source code and have looked at it in order to improve our program. You do not need to wait for us to publish. The science fair is not until next year so we have a lot of time to get everything just right and then move the code on to a GPU.

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

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

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

Quote from: Telariust

At this time, I will try to write addition in affine coordinates, which is the fastest way, +30% expected speed-up.

Quote from: Telariust

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..
after which do not need to spend 8M,3S, only nearly 20M to each 1I, it +35% speed-up

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

Code:

[pow2bits] 2^50
[range] 2^49..2^50 ; W = U - L = 0x0002000000000000 (2^49)

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

Code:

 --> [0y 0m 0d 00:09:16s] [0.27Mk/s] [0y 0m 0d 00:00:00s]
[i] 152944440j; DP T+W=4+6=10; dp/kgr=5.0;
[prvkey#50] 00000000000000000000000000000000000000000000000000022BD43C2E9354
[#############################; passtime: 0y 0m 0d 00:09:16s]
[####################################; precision: 556s 699ms]

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

Code:

 --> [0y 0m 0d 00:08:42s] [0.29Mk/s] [0y 0m 0d 00:00:00s]
[i] 152944440j; DP T+W=4+6=10; dp/kgr=5.0;
[prvkey#50] 00000000000000000000000000000000000000000000000000022BD43C2E9354
[#############################; passtime: 0y 0m 0d 00:08:42s]
[####################################; precision: 522s 492ms]

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

Code:

// 0: A + A -> A,  xA ready ; 0.291Mk/s; the fastest
// 1: J + A -> J,  xJ->xA   ; 0.274Mk/s; secp256k1_gej_add_ge_var()
// 2: J + A -> J,  xJ->xA   ; 0.267Mk/s; secp256k1_gej_add_ge()
// 3: 0*P0+k*G->J, xJ->xA   ; 0.091Mk/s; secp256k1_ecmult()
// 4: k*G->J, J+J->J, xJ->xA; 0.031Mk/s; secp256k1_ecmult_gen() + secp256k1_gej_add_var()

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)

Code:

// 2A -> A (1I, 2M, 2S)
void secp256k1_ge_double_var(secp256k1_ge *r, const secp256k1_ge *a){

	secp256k1_fe rX, rY;
	secp256k1_fe tmp1, tmp2;

	tmp1 = a->y;
	if ( (a->infinity == 1) || secp256k1_fe_normalizes_to_zero_var(&tmp1) ) { 
		secp256k1_ge_set_infinity(r);
		return;
	}

	// s = (3x^2 + A)/(2y)				# 1I 2M 1S
	// A=0 B=7 (secp256k1)
	secp256k1_fe_sqr(&tmp2, &a->x);//1S
	tmp1 = tmp2;
	secp256k1_fe_add(&tmp1, &tmp2);
	secp256k1_fe_add(&tmp1, &tmp2);
	secp256k1_fe_normalize_weak(&tmp1);

	tmp2 = a->y;
	secp256k1_fe_add(&tmp2, &a->y);
	secp256k1_fe_normalize_weak(&tmp2);
	secp256k1_fe_inv_var(&tmp2, &tmp2);//1I

	secp256k1_fe_mul(&tmp1, &tmp1, &tmp2);//1M

	// x' = s^2-2x					# 1S
	secp256k1_fe_sqr(&rX, &tmp1);//1S
	tmp2 = a->x;
	secp256k1_fe_add(&tmp2, &a->x);
	secp256k1_fe_negate(&tmp2, &tmp2, 1);
	secp256k1_fe_add(&rX, &tmp2);
	secp256k1_fe_normalize_weak(&rX);

	// y' = s(x-x')-y				# 1M
	secp256k1_fe_negate(&tmp2, &rX, 1);
	rY = a->x;
	secp256k1_fe_add(&rY, &tmp2);
	secp256k1_fe_normalize_weak(&rY);
	secp256k1_fe_mul(&rY, &rY, &tmp1);//1M
	secp256k1_fe_negate(&tmp2, &a->y, 1);
	secp256k1_fe_add(&rY, &tmp2);
	secp256k1_fe_normalize_weak(&rY);

	r->x = rX;
	r->y = rY;
}


// A + A -> A (1I, 2M, 1S)
void secp256k1_ge_add_ge_var(secp256k1_ge *r, const secp256k1_ge *a, const secp256k1_ge *b){
	

	if ( (a->infinity == 1) || (b->infinity == 1) ) { 
		if ( (a->infinity == 1) ^  (b->infinity == 1) ) {
			if (a->infinity == 1) { r->x = b->x; r->y = b->y; return; }
			if (b->infinity == 1) { r->x = a->x; r->y = a->y; return; }
		}else{
			secp256k1_ge_set_infinity(r);
			return;
		}
	}

	secp256k1_fe rX, rY;
	secp256k1_fe tmp1, tmp2;

	secp256k1_fe aXneg;
	secp256k1_fe_negate(&aXneg, &a->x, 1);
	secp256k1_fe aYneg;
	secp256k1_fe_negate(&aYneg, &a->y, 1);

	//dx = B.x - A.x
	tmp1 = b->x;
	secp256k1_fe_add(&tmp1, &aXneg);

	//dy = B.y - A.y
	tmp2 = b->y;
	secp256k1_fe_add(&tmp2, &aYneg);


	if (secp256k1_fe_normalizes_to_zero_var(&tmp1)) {
		if (secp256k1_fe_normalizes_to_zero_var(&tmp2)) {
			secp256k1_ge_double_var(r, a);
			return;
		}else{
			secp256k1_ge_set_infinity(r);
			return;
		}
	}

	secp256k1_fe_normalize_weak(&tmp1);
	secp256k1_fe_normalize_weak(&tmp2);

	secp256k1_fe_inv_var(&tmp1, &tmp1);//1I

	//c = dy * invert(dx, p) % p			# 1I,1M
	secp256k1_fe c;
	secp256k1_fe_mul(&tmp2, &tmp2, &tmp1);//1M

	//R.x = (c**2 - A.x - B.x) % p			# 1S
	secp256k1_fe_sqr(&rX, &tmp2);//1S
	secp256k1_fe_add(&rX, &aXneg);
	secp256k1_fe_negate(&tmp1, &b->x, 1);
	secp256k1_fe_add(&rX, &tmp1);
	secp256k1_fe_normalize_weak(&rX);

	//R.y = (c*(A.x - R.x) - A.y) % p		# 1M
	rY = a->x;
	secp256k1_fe_negate(&tmp1, &rX, 1);
	secp256k1_fe_add(&rY, &tmp1);
	secp256k1_fe_normalize_weak(&rY);
	secp256k1_fe_mul(&rY, &rY, &tmp2);//1M
	secp256k1_fe_add(&rY, &aYneg);
	secp256k1_fe_normalize_weak(&rY);

	r->x = rX;
	r->y = rY;
}

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

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

Quote from: Telariust

Quote from: 57fe

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

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;

Telariust

jr. member

Activity: 38

Merit: 18

Quote from: BurtW on September 10, 2019, 04:20:51 PM

static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *gn)
...
#define ec_point_mul_and_add(r,a,n) {

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

Quote

1899. Mr. Deull's most famous attributed utterance is that "everything that can be invented has been invented."

I bet your experiments with ECMULT_WINDOW_SIZE didn’t give anything, because secp256k1_ecmult_gen() doesn’t use it Cheesy

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()

Code:

//secp256k1_context *ctx = secp256k1_context_create(SECP256K1_CONTEXT_NONE);
secp256k1_context *ctx = secp256k1_context_create(SECP256K1_CONTEXT_SIGN | SECP256K1_CONTEXT_VERIFY);

// ecmult vars
secp256k1_scalar scalarK; secp256k1_scalar_set_int(&scalarK, 123456);
secp256k1_scalar scalar0; secp256k1_scalar_set_int(&scalar0, 0);
secp256k1_gej point_0gej; secp256k1_gej_set_infinity(&point_0gej);

// jacobian base point G
secp256k1_gej secp256k1_gej_const_g;
secp256k1_gej_set_ge(&secp256k1_gej_const_g, &secp256k1_ge_const_g);

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

I was interested to compare these functions.

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

Code:

make clean
./autogen.sh
./configure --enable-ecmult-static-precomputation  --with-bignum=gmp --with-scalar=64bit --with-field=64bit --with-asm=x86_64 
make

default ECMULT_WINDOW_SIZE = 15

########

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

Code:

for(uint64_t i = 1; i<1000000 ; ++i){
	secp256k1_scalar_set_uint64(&scalarK, i); // sequential points
	MULT_FUNCTION_HERE(&context, point_jacobian, &scalarK)
}

results of benchmark

Code:

		//// Multiply: R = q*A (in constant-time)
		secp256k1_ecmult_const(&TestGej, &secp256k1_ge_const_g, &scalarK, 256);

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

Code:

	//// Multiply: R = a*G (with the generator)
	//// To harden against timing attacks .. Break up the multiplicand into groups of..
	secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &TestGej, &scalarK);

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

Code:

		//// R = na*A + ng*G
		//// secp256k1_ecmult(*ctx, gej *r, const gej *a, const scalar *na, const scalar *ng);
		//secp256k1_ecmult(&ctx->ecmult_ctx, &TestGej, &secp256k1_gej_const_g,	&scalarK,	NULL); // NULL not recommended!
		secp256k1_ecmult(&ctx->ecmult_ctx, &TestGej, &secp256k1_gej_const_g,	&scalarK,	&scalar0); // k*G + 0*G

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

same function, another

Code:

		//// R = na*A + ng*G
		//secp256k1_ecmult(&ctx->ecmult_ctx ,&TestGej, NULL,			&scalar0,	&scalarK); // NULL not recommended!
		secp256k1_ecmult(&ctx->ecmult_ctx, &TestGej, &point_0gej,		&scalar0,	&scalarK); // 0*P0 + k*G

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:

Code:

for(uint64_t i = 1; i<1000000 ; ++i){
	secp256k1_scalar_set_uint64(&scalarK, TestGej.x.n[0]); // pseudo random points
	MULT_FUNCTION_HERE(&context, point_jacobian, &scalarK)
}

results of benchmark

Code:

		secp256k1_ecmult_const(&TestGej, &secp256k1_ge_const_g, &scalarK, 256);

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

Code:

	secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &TestGej, &scalarK);

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

Code:

		secp256k1_ecmult(&ctx->ecmult_ctx, &TestGej, &secp256k1_gej_const_g,	&scalarK,	&scalar0); // k*G + 0*G

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

same function, another

Code:

		secp256k1_ecmult(&ctx->ecmult_ctx, &TestGej, &point_0gej,		&scalar0,	&scalarK); // 0*P0 + k*G

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)

########

Quote from: Telariust

..multiplication points is very expensive, more expensive than the slowest addition points.

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

Code:

for(uint64_t i = 1; i<1000000 ; ++i){
	ADD_FUNCTION_HERE(&result_point_jacobian, 1point_jacobian, 2point_affine)
}

results of benchmark

Code:

		secp256k1_gej_add_ge(&TestGej, &TestGej, &secp256k1_ge_const_g);

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

Code:

		secp256k1_gej_add_ge_var(&TestGej, &TestGej, &secp256k1_ge_const_g, NULL);

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

Code:

		secp256k1_gej_double_var(&TestGej, &TestGej, NULL);

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

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Thanks for all your input. We are reading it over carefully to see what we can use in our project and will get back to you.

We have already rewritten the following functions to make them as fast as possible:

static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *gn)
SECP256K1_INLINE static int secp256k1_scalar_reduce(secp256k1_scalar *r, unsigned int overflow)
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)

We are working on rewriting:

static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_ge *b)

Our internal function

Code:

#define ec_point_mul_and_add(r,a,n)    
{ 
    secp256k1_gej rj; 
    secp256k1_ecmult_gen(&ecgrp->ecmult_gen_ctx, &rj, n);  // highly optimized
    secp256k1_gej_add_ge_var(&rj, &rj, a, NULL); // optimization is work in progress
    secp256k1_ge_set_gej_var(r, &rj); 
}

We heavily rely on and use the following observation to inform our parameter choices:

Code:

If the PRF is defined as follows:

    x = 1 << (X % m)

The PRF will generate one of the numbers: 2**0, 2**1, .., 2**(m-1) with equal probability

So the average hop distance as a function of m can be calculated as follows:

    ahd = (1/m)(2**0) + (1/m)(2**1) + .. + (1/m)(2**(m-1))
        = (1/m)[(2**0) + (2**1) + .. + (2**(m-1))]
        = (1/m)[(2**m) - 1]
        = ((2**m) - 1)/m

Therefore the entire distance hopped by the kangaroo, given nn hops, can be estimated as:

    c = nn(ahd)
      = (nn/m)((2**m) - 1)

Telariust

jr. member

Activity: 38

Merit: 18

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

Code:

# get JmaxofSp
def getJmaxofSp(optimalmeanjumpsize, dS):
	if flag_verbose > 0: 
		print('[optimal_mean_jumpsize] %s' % optimalmeanjumpsize)

	sumjumpsize = 0

	for i in range(1,len(dS)):

		#sumjumpsize = (2**i)-1
		#sumjumpsize += 2**(i-1)
		sumjumpsize += dS[i-1]

		now_meanjumpsize	= int(round(1.0*(sumjumpsize)/(i)))

		#next_meanjumpsize	= int(round(1.0*(sumjumpsize+2**i)/(i+1)))
		next_meanjumpsize	= int(round(1.0*(sumjumpsize+dS[i])/(i+1)))

		if flag_verbose > 1: 
			print('[meanjumpsize#Sp[%d]] %s(now) <= %s(optimal) <= %s(next)' % (i, now_meanjumpsize, optimalmeanjumpsize, next_meanjumpsize ))


		if  optimalmeanjumpsize - now_meanjumpsize <= next_meanjumpsize - optimalmeanjumpsize : 
			if flag_verbose > 0: 
				print('[meanjumpsize#Sp[%d]] %s(now) <= %s(optimal) <= %s(next)' % (i, now_meanjumpsize, optimalmeanjumpsize, next_meanjumpsize ))

			if flag_verbose > 0: 
				print('[JmaxofSp] Sp[%s]=%s nearer to optimal mean jumpsize of Sp set' % (i, now_meanjumpsize))

			return i

	print("\n[FATAL_ERROR] JmaxofSp not defined!\n"); exit(-1)

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

Quote from: Firebox on September 10, 2019, 04:01:32 AM

Quote from: BurtW on September 09, 2019, 10:56:42 AM

We have updated the OP with our latest results. Here is a summary of the results of runs for tests 0 through 49:...

That is already good result!

no, absolutely not

August 26, 2019

Code:

pkey    Standard OpenSSL library     secp256k1 (S 8X32, F 10X26)
bits   hops/second   test run time   hops/second   test run time
====   ===========================   =========================== 
  31   1942.378857   28.4496 secs    5520.634781   10.0240 secs

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

September 09, 2019 (secp256k1)

Code:

test       time         hps       hops
----  --------------  -------  ----------
31    9.2328 secs    11,884  109705

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)

Quote from: arulbero on February 27, 2019, 02:25:46 PM

Are you using affine or jacobian coordinates for the points?

~~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://bitcointalksearch.org/topic/m.52068840
..so you can’t store several million pre-calculated points in memory. it explains your choice.

Quote

x = PRF(X)
= 1 << (X % m)
...
ec_point_mul_and_add(r,a,n)

not mask, i see,.. then simple, u tried built classic pattern of a*b+c

Quote

..rewritten the following functions..

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.

Firebox

jr. member

Activity: 59

Merit: 3

Quote from: BurtW on September 09, 2019, 10:56:42 AM

We have updated the OP with our latest results. Here is a summary of the results of runs for tests 0 through 49:...

That is already good result!
When will be the first release?

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

We have updated the OP with our latest results. Here is a summary of the results of runs for tests 0 through 49:

Code:

test       time         hps       hops       compares    mem(bytes)    total time     time hopping   not hopping
----  --------------  -------  ----------  ------------  ----------  --------------  --------------  -----------
   0    0.3237 msecs   10,504  1           3             1032                   323              95          228
   1    0.2853 msecs   11,062  1           3             1032                   285              90          194
   2    0.2785 msecs   11,111  1           3             1032                   278              90          188
   3    1.8730 msecs   11,271  8           10            1032                 1,873             709        1,163
   4    1.8351 msecs   11,147  11          13            1032                 1,835             986          848
   5    2.1243 msecs   11,123  15          17            1032                 2,124           1,348          775
   6    5.2260 msecs   11,069  52          54            1032                 5,226           4,697          528
   7    3.9406 msecs   11,065  32          34            1032                 3,940           2,891        1,048
   8    4.6425 msecs   10,174  45          47            1032                 4,642           4,423          219
   9   46.8674 msecs   11,052  510         512           1032                46,867          46,146          721

  10   84.2980 msecs   10,674  893         895           1032                84,298          83,661          636
  11  122.2013 msecs   11,662  1413        1415          1032               122,201         121,162        1,039
  12  257.2438 msecs   11,579  2976        2978          1032               257,243         257,019          224
  13  514.6517 msecs   11,402  5840        5842          1032               514,651         512,196        2,455
  14  501.1961 msecs   11,791  5901        5903          1032               501,196         500,466          729
  15    1.1839 secs    11,886  14026       14028         1032             1,183,908       1,180,079        3,829
  16    3.0370 secs    11,631  35249       35251         1032             3,037,005       3,030,586        6,419
  17    5.6526 secs    11,230  63475       63477         1032             5,652,638       5,652,025          613
  18   14.0759 secs    11,847  166753      166755        1032            14,075,930      14,075,708          222
  19   15.5404 secs    11,922  185259      185261        1032            15,540,417      15,539,472          945

  20  742.1446 msecs   11,882  8804        5677          32088              742,144         740,944        1,200
  21  475.1973 msecs   11,881  5627        1903          32696              475,197         473,623        1,574
  22  561.2366 msecs   11,555  6359        3169          33912              561,236         550,304       10,932
  23  428.6246 msecs   11,867  5044        1167          36344              428,624         425,047        3,577
  24    2.2156 secs    11,842  26026       22985         41208            2,215,606       2,197,825       17,780
  25  350.9793 msecs   11,864  4025        695           50936              350,979         339,275       11,704
  26  650.9386 msecs   11,695  7326        4443          70392              650,938         626,434       24,504
  27   11.2562 secs    11,793  132214      128675        109304          11,256,223      11,211,378       44,845
  28    4.5728 secs    11,819  52883       49679         187128           4,572,770       4,474,294       98,476
  29    4.2294 secs    11,907  48300       45216         342776           4,229,449       4,056,522      172,927

  30   10.6122 secs    11,759  124766      56010         62808           10,612,244      10,610,509        1,735
  31    9.2328 secs    11,884  109705      41191         63416            9,232,760       9,231,168        1,592
  32   14.3117 secs    11,922  170592      103053        64632           14,311,717      14,309,552        2,165
  33   55.8702 secs    11,902  664893      596368        67064           55,870,151      55,862,085        8,066
  34   22.1413 secs    11,923  263922      195453        71928           22,141,326      22,135,223        6,103
  35    1.0531 mins    11,927  753508      683623        81656           63,186,883      63,175,281       11,602
  36   28.3459 secs    11,924  337734      269198        101112          28,345,873      28,323,662       22,210
  37    9.2387 mins    11,860  6573832     6505951       140024         554,319,152     554,275,660       43,492
  38   11.2025 secs    11,926  132534      64338         217848          11,202,535      11,113,380       89,154
  39    4.5557 mins    11,925  3257543     3189102       373496         273,342,973     273,170,580      172,393

  40   13.1216 mins    11,927  9389808     7285993       124248         787,294,602     787,289,468        5,133
  41   10.3313 mins    11,929  7394352     5292081       124856         619,880,117     619,878,329        1,787
  42    3.8015 mins    11,935  2722138     620876        126072         228,090,413     228,087,570        2,842
  43    5.7648 mins    11,924  4124314     2019820       128504         345,888,060     345,884,231        3,828
  44    3.2043 mins    11,930  2293481     193018        133368         192,258,803     192,252,406        6,397
  45   33.9166 mins    11,919  24254078    22153676      143096       2,034,994,703   2,034,982,887       11,815
  46   47.9810 mins    11,922  34321486    32221012      162552       2,878,859,972   2,878,832,117       27,854
  47    2.4000 hours   11,918  102968649   100868429     201464       8,639,864,920   8,639,820,958       43,962
  48    4.1320 hours   11,924  177371081   175268406     279288      14,875,131,910  14,875,045,149       86,760
  49   23.9987 hours   11,914  1029325281  1027225432    434936      86,395,345,966  86,395,170,751      175,214
      ==============   ======                                        ==============  ==============  ===========
                       11,630                                       118,106,695,147 118,105,560,480    1,134,666

Where

Code:

test          test number
time          run time needed to find the private key
hps           hops per second (averaged 11,630 on my laptop with a highly modified secp256k1 library)
hops          total number of hops it took to find the private key
cmps          total number of point comparisons it took to find the private key
mem           amount of memory dynamically allocated during the run
total time    total run time in msec
time hopping  total time spent hopping in msec
not hopping   the overhead (time not hopping) in msec

racminer

member

Activity: 245

Merit: 17

Quote from: brainless on September 04, 2019, 02:29:45 PM

Quote from: ?? on ??

I have tried the python code on linux and windows with or without gmpy2.
I was able to retrieve all known private keys (up to case 100) with linux python.
However when using windows things go wrong beyond case 59.
For exemple
case 60 ... the private key should be 0xFC07A1825367BDA but I get 0xFC07A1825367BXX with XX a random number
case 61 ... the private key should be 0x13C96A3742F64906 but I get 0x13C96A3742F64XXX with XXX a random number
case 63 ... the private key should be 0x7CCE5EFDACCF6808 but I get 0x7CCE5EFDACCF6XXX with XXX a random number
etc ...

This bug persists even without gmpy2 !!!

I am working on it Grin

What hardware do you use and how long it took to crack 100?

To check all known private keys, I changed the code to search within a given range [a, b], not necessarily the whole range. For instance, private key for case 100 is 0xaf55fc59c335c8ec67ed24826, so if I run my modified python script for range [ 0xaf55fc59c335c8e0000000000, 0xaf55fc59c335c8f0000000000 ], I get the answer in less than half a minute.

like to share modifed script for search range ?

See here: https://bitcointalksearch.org/topic/m.52375040

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

I am up for testing also? It is live on GitHub yet?

Quote from: asher1101 on August 31, 2019, 02:03:43 PM

Hello, I am glad to participate in this project.
Regarding the Elliptic Curve, I think there is a weakness in the current Algorithm.

Quote from: ?? on ??

Also, I'm interested in testing... the fpga port.
I realise that is a far way off, and I'm willing to help with the development if you and your daughter are open to the idea.

You have been added to the list of possible testers. See the OP of this thread.

Quote from: ?? on ??

Whatup whatup, all doing their own test, nice to have something to test on a pkey or address,
how should i know how it works, i don't know, any news fpga or gpu or cpu dont matter, i'm in,
systems ready, got two days off,
so love peace out,

You are already on the list. We are still working on our first release of code.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

Does anyone know why this post has been erased? it is still here because "brainless" quoted it?

Yes, your entire conversation is still in the thread, again:

Please note that since this thread will be used as reference material in a science fair project we delete most posts in this thread just to keep it clean.

In other words, once a post is quoted then we delete the original post.

Your posts will all still be in the thread.

The thread stays shorter and cleaner this way.

I hope this is not an issue for anyone. It is just to keep the thread as short and clean as possible. It is not because we do not appreciate your posts.

We do!

Thanks!

brainless

member

Activity: 348

Merit: 34

Quote from: ?? on ??

I have tried the python code on linux and windows with or without gmpy2.
I was able to retrieve all known private keys (up to case 100) with linux python.
However when using windows things go wrong beyond case 59.
For exemple
case 60 ... the private key should be 0xFC07A1825367BDA but I get 0xFC07A1825367BXX with XX a random number
case 61 ... the private key should be 0x13C96A3742F64906 but I get 0x13C96A3742F64XXX with XXX a random number
case 63 ... the private key should be 0x7CCE5EFDACCF6808 but I get 0x7CCE5EFDACCF6XXX with XXX a random number
etc ...

This bug persists even without gmpy2 !!!

I am working on it Grin

What hardware do you use and how long it took to crack 100?

To check all known private keys, I changed the code to search within a given range [a, b], not necessarily the whole range. For instance, private key for case 100 is 0xaf55fc59c335c8ec67ed24826, so if I run my modified python script for range [ 0xaf55fc59c335c8e0000000000, 0xaf55fc59c335c8f0000000000 ], I get the answer in less than half a minute.

like to share modifed script for search range ?

racminer

member

Activity: 245

Merit: 17

Quote from: ?? on ??

Terminology for the science fair project

-------------------------
-------------------------

0x034AF4B81F8C450C2C870CE1DF184AFF1297E5FCD54944D98D81E1A545FFB22596
54 bit

222872.369 h/s
223958.708 h/s
---------------
230794.045 h/s
230895.206 h/s
230857.369 h/s

What is your PC configuration ?

intel i3-6100, 8gb ddr4 ram, ubuntu 18.x

It runs at 3.7GHz ... that explains your rate ...

racminer

member

Activity: 245

Merit: 17

Finally I got gmpy2 installed on windows Roll Eyes

Thanks to this site : "https://www.lfd.uci.edu/~gohlke/pythonlibs/" which provides unofficial Windows binaries for Python Extension Packages.

Code:

 
D:\newwork\python>python kang.py
P-table prepared
tame and wild herds are prepared
115378.321 h/s
115352.684 h/s
113976.331 h/s
total time: 18.41 sec
SOLVED: 1003651412950
Hops: 2101873
tame and wild herds are prepared
112978.446 h/s
112514.481 h/s
105994.030 h/s
total time: 34.77 sec
SOLVED: 1003651412950
Hops: 1799360
tame and wild herds are prepared
110405.305 h/s
110319.404 h/s
113115.999 h/s
114104.774 h/s
114309.523 h/s
112088.956 h/s
110844.133 h/s
113467.999 h/s
112101.691 h/s
total time: 81.57 sec
SOLVED: 1003651412950
Hops: 5249192
3050141.6666666665 +/- 1102987.655596129
Average time to solve: 27.19 sec

My modest config: Intel(R) Core(TM) i7-2670QM CPU @2.20GHz 16Gb (Dell Inspiron N5110)

Without gmpy2, I was getting some 8000 h/s ...

for example, if you are running windows 10 64 bit and you have python 3.7 installed, download this file : gmpy2-2.0.8-cp37-cp37m-win_amd64.whl from the site above and do:

pip install gmpy2-2.0.8-cp37-cp37m-win_amd64.whl

Next
0) uncomment ligne 3 (import gmpy2)
1) uncomment ligne 45 (c = dy * gmpy2.invert(dx, p) % p)
2) comment ligne 45 (#c = dy * rev(dx, p) % p )

good luck !

Ooops !!! , I saw this afteward ...

https://bitcointalk.org/index.php?topic=5166284.260 from Telariust

asher1101

newbie

Activity: 17

Merit: 2

Hello, I am glad to participate in this project.
Regarding the Elliptic Curve, I think there is a weakness in the current Algorithm.

Firebox

jr. member

Activity: 59

Merit: 3

Quote from: Mangal99 on August 29, 2019, 10:28:12 AM

Quote from: ?? on ??

To Firefox:
At startup files wild.txt & tame.txt were also empty, but after 2 days of work has appeared a few lines.

Does that mean that kargaroo jumps appears very late?

I think yes. Puzzle # 105 has a lot of difficulty.
Obviously, you need a version of the program on the GPU. There are already several programs for computing using the Pollard algorithm on the GPU, but they are not in the public domain.
Also on freelance sites there are several orders for the development of such programs on CUDA and OpenCL. Budget from 300 to 1000 dollars.
Maybe someone will share or sell a similar program.

That is the problem, that versions of the script which are capable to use a GPU resources are available only for money.
If any of it realy exist... I have a huge doubt! Otherwise why to sell it if you have it )). Take a fu****g loan in the bank, rent any huge cloud GPU VPS and open all addresses with available PUBKEY. That it!
But as far as we can see, since this scripts were anounced none of the 100+ addresses was openned, so looks like or it doesn't work or it's fake.)))

Anyhow, hopefully a good part of community soon will release an open source version on such script. Fingers crossed!

Mangal99

newbie

Activity: 4

Merit: 0

Quote from: ?? on ??

To Firefox:
At startup files wild.txt & tame.txt were also empty, but after 2 days of work has appeared a few lines.

Does that mean that kargaroo jumps appears very late?

I think yes. Puzzle # 105 has a lot of difficulty.
Obviously, you need a version of the program on the GPU. There are already several programs for computing using the Pollard algorithm on the GPU, but they are not in the public domain.
Also on freelance sites there are several orders for the development of such programs on CUDA and OpenCL. Budget from 300 to 1000 dollars.
Maybe someone will share or sell a similar program.

Firebox

jr. member

Activity: 59

Merit: 3

Quote from: Darmont33 on August 22, 2019, 10:30:58 AM

Quote from: ?? on ??

Who need some code, I have it for Python 2.7!
This is my own code and I apologize for absolutely no-PEP. And for my English, I apologize too.
The code is not so fast, but my estimation is more optimistic - only 10000 years on average for the problem 105.
Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code.

The code is on my WebSite:
http://fe57.org/forum/thread.php?board=4&thema=1#1

This is my main interest. You are now informed that my site exists in the Universe!
To be more interesting: test problem 75 from pickachunakapika to drotika solution:
26970178626862821196031
(decimal)
I guess that the solution can be posted now because all deadlines are finished. Or I miss something and drotika was already posted the answer.

Very nice

For those who use python3, you may have to change a few things for the code to work:

1) for all print statements you need (), for example line 60
change this > print 'prime must be 3 modulo 4'
to this > print ('prime must be 3 modulo 4')

2) make sure you distinguish between integer division // and float division /
for example, line 63
change this > pw = (p + 1) / 4
to this > pw = (p + 1) // 4

For case 32 I get
P-table prepared
tame and wild herds are prepared
6091.198 h/s
6119.991 h/s
6047.619 h/s
6028.418 h/s
6020.816 h/s
5995.830 h/s
6041.220 h/s
6026.008 h/s
6077.185 h/s
total time: 45.38 sec
SOLVED: 3093472814
Hops: 273742
tame and wild herds are prepared
5995.223 h/s
6044.420 h/s
5966.429 h/s
6050.819 h/s
total time: 68.41 sec
SOLVED: 3093472814
Hops: 137749
tame and wild herds are prepared
6038.017 h/s
5968.435 h/s
total time: 82.83 sec
SOLVED: 3093472814
Hops: 85546
165679.0 +/- 56093.66357263537
Average time to solve: 27.61 sec

Hi, how did you change line 160 for python 3?

if you mean this line:

print '%.3f h/s'%((Hops-Hops_old)/(t1-t0))
just add parenthesis
print ('%.3f h/s'%((Hops-Hops_old)/(t1-t0)))
do the same for all print statements.

Now everything works!
I didn’t put it there ()
thank Wink

I have installed gmpy2 module v.2.0.8 and got a good results, speed increased from ~6k h/s till ~150k h/s and for e.g. #45 solved in ~100sec. But when I run the same script for e.g. #105 files wild.txt & tame.txt are empty ((.
When you, guys, run this script for the #105 addr, do your files wild.txt & tame.txt being filled-up with any data?
If yes share pls your version of script.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

I draw your attention, secp256k1_scalar_set_int() has x32-x64 problem
my fix

Code:

void secp256k1_scalar_set_uint64(secp256k1_scalar *r, uint64_t v){
    #if defined(USE_SCALAR_4X64)
	r->d[0] = v;
	r->d[1] = r->d[2] = r->d[3] = 0;
    #elif defined(USE_SCALAR_8X32)
	r->d[0] = (uint32_t)(v);
	r->d[1] = (uint32_t)(v>>32);
	r->d[2]=r->d[3]=r->d[4]=r->d[5]=r->d[6]=r->d[7]=0;
    #endif
}

I must probably unsubscribe to the developers

I completely forgot
maybe your problems grow from here.

We also found this issue and also quickly created our own functions to get it to work. We also called our new functions secp256k1_scalar_set/get_uint64 so I guess great minds think alike! Wink

We were just trying to quickly get everything to work so we have not optimized anything yet. Our function was:

Code:

static uint64_t secp256k1_scalar_get_uint64(secp256k1_scalar * a)
{
    uint8_t b32[32];
    secp256k1_scalar_get_b32(b32, a);

    const uint64_t ret =
        ((uint64_t)b32[24] << 56 ) |
        ((uint64_t)b32[25] << 48 ) |
        ((uint64_t)b32[26] << 40 ) |
        ((uint64_t)b32[27] << 32 ) |
        ((uint64_t)b32[28] << 24 ) |
        ((uint64_t)b32[29] << 16 ) |
        ((uint64_t)b32[30] <<  8 ) |
        ((uint64_t)b32[31] <<  0 ) ;

    return ret;
}

Obviously yours is much better/faster so we have replaced ours with yours. Thanks!

Quote from: ?? on ??

Quote from: BurtW on August 26, 2019, 05:23:54 PM

ENDOMORMPHSIM

Endomorphism is implemented here only to accelerate the signing of the transaction, so do not expect this to accelerate the usual multiplication.

When we ran our benchmark there was no difference. That explains it, so thanks. We have turned off this flag since it does not help us.

Quote from: ?? on ??

Quote from: BurtW on August 26, 2019, 05:23:54 PM

We currently have ECMULT_WINDOW_SIZE set to 15. Does anyone know how changing this setting will affect performance?

table #1
eprint.iacr.org/2016/103.pdf
The size of a pre-computed table in memory is created just for this. Speeds up multiplication in exchange for RAM.
Ryan also used the increased size -w 18/20/22/24.. in the brainflayer.
ECMULT_WINDOW_SIZE?
maybe ECMULT_TABLE_SIZE with WINDOW_G?
ecmult_impl.h

Code:

#else
/** One table for window size 16: 1.375 MiB. */
#define WINDOW_G 16
#endif

Quote from: ?? on ??

Quote from: BurtW on August 26, 2019, 05:23:54 PM

We currently have ECMULT_WINDOW_SIZE set to 15. Does anyone know how changing this setting will affect performance?

questions like these can only be answered with a well designed benchmark.
in this case you have to measure how long it takes to do the precomputation with different values ∈ [2, 24] and how that compares with the rest of computation. if the rest is significantly longer then it can justify that long initial precomputation and allocation of memory.

Thanks for the very useful information. We will play with this setting in the future.

We also found this in the code:

Code:

/** Larger values for ECMULT_WINDOW_SIZE result in possibly better
 *  performance at the cost of an exponentially larger precomputed
 *  table. The exact table size is
 *      (1 << (WINDOW_G - 2)) * sizeof(secp256k1_ge_storage)  bytes,
 *  where sizeof(secp256k1_ge_storage) is typically 64 bytes but can
 *  be larger due to platform-specific padding and alignment.
 *  If the endomorphism optimization is enabled (USE_ENDOMORMPHSIM)
 *  two tables of this size are used instead of only one.
 */
#  define WINDOW_G ECMULT_WINDOW_SIZE

/* Noone will ever need more than a window size of 24. The code might
 * be correct for larger values of ECMULT_WINDOW_SIZE but this is not
 * not tested.
 *
 * The following limitations are known, and there are probably more:
 * If WINDOW_G > 27 and size_t has 32 bits, then the code is incorrect
 * because the size of the memory object that we allocate (in bytes)
 * will not fit in a size_t.
 * If WINDOW_G > 31 and int has 32 bits, then the code is incorrect
 * because certain expressions will overflow.
 */
#if ECMULT_WINDOW_SIZE < 2 || ECMULT_WINDOW_SIZE > 24
#  error Set ECMULT_WINDOW_SIZE to an integer in range [2..24].
#endif

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

We now have a compile time switch between OpenSSL, secp256k1(SCALAR_8X32, FIELD_10X26), secp256k1(SCALAR_4X64, FIELD_5X52), and secp256k1(SCALAR_4X64, FIELD_5X52, ENDOMORMPHSIM). Here is the run time and hops per second comparison for the 32 unit tests:

Code:

pkey    Standard OpenSSL library     secp256k1 (S 8X32, F 10X26)    secp256k1(S 4X64, F 5X52)    secp256k1(S4X64, F5X52, EM)
bits   hops/second   test run time   hops/second   test run time   hops/second   test run time   hops/second   test run time
====   ===========================   ===========================   ===========================   ===========================
   1   2003.205128    6.0950 msecs   5114.435494    6.3592 msecs   4318.255425    6.4021 msecs   5269.397971    5.8835 msecs
   2   1757.199025    8.3635 msecs   4655.764418    7.8586 msecs   5142.049107    7.0887 msecs   4802.497299    7.6262 msecs
   3   1716.811880    5.9904 msecs   5003.752815    6.9754 msecs   5110.514884    6.0526 msecs   4268.487888    6.8087 msecs
   4   1960.438354   26.3895 msecs   5092.427560   27.7752 msecs   5187.260089    7.4309 msecs   4996.252810    7.7770 msecs
   5   1880.119970   30.0658 msecs   5013.009954   31.3478 msecs   5215.318134    9.4163 msecs   5236.254831    9.7029 msecs
   6   1608.708475   30.6862 msecs   4410.467510   30.2971 msecs   4926.917392   22.3417 msecs   5644.933672   20.1065 msecs
   7   1866.896315   34.8628 msecs   5558.843043   31.2577 msecs   5131.685676   21.5328 msecs   5181.347150   20.9325 msecs
   8   1990.502460   31.4858 msecs   5039.596832   30.4067 msecs   4838.430966   20.6268 msecs   5072.279990   28.5510 msecs
   9   1928.760658   40.3494 msecs   4950.639215   41.2204 msecs   5260.714838   22.1908 msecs   5241.170939   20.5226 msecs
  10   1890.373754   81.8738 msecs   5256.467332   57.0551 msecs   5429.994625   32.7629 msecs   5453.290894   41.4165 msecs
  11   1694.971872  101.2429 msecs   4763.924918   61.4267 msecs   5340.172912   41.3388 msecs   5439.249145   46.5306 msecs
  12   1858.940556    1.0718 secs    5145.349959  527.2134 msecs   5326.737472  410.4776 msecs   5221.758623  434.4509 msecs
  13   1895.071971   51.6923 msecs   5386.060874   38.1821 msecs   5233.349227   23.4991 msecs   5373.390968   31.1977 msecs
  14   1908.767643  896.4858 msecs   5082.972044  385.9540 msecs   5430.446276  321.9922 msecs   5441.145301  317.7290 msecs
  15   1939.352878  439.6496 msecs   5326.381969  195.0367 msecs   5488.742759  160.9818 msecs   5420.695712  179.5955 msecs
  16   1918.732814  530.3667 msecs   5258.277326  219.2995 msecs   5510.868625  188.6750 msecs   5466.555751  201.7339 msecs
  17   1895.048388  205.8168 msecs   5430.753319   95.6410 msecs   5453.448080   79.5526 msecs   5339.284536   85.5150 msecs
  18   1930.620117    1.3492 secs    5136.760660  546.6825 msecs   5545.967087  474.6491 msecs   5433.455762  484.8219 msecs
  19   1959.292325  594.2687 msecs   5364.976931  228.5351 msecs   5407.810389  219.3399 msecs   5489.027106  219.1785 msecs
  20   1937.090596    1.2060 secs    5519.443944  438.4141 msecs   5567.924674  427.1013 msecs   5487.179193  432.8127 msecs
  21   1934.545311    2.1349 secs    5493.508717  774.8660 msecs   5504.112724  758.1783 msecs   5469.417987  766.5974 msecs
  22   1929.260673    3.4962 secs    5376.994864    1.2774 secs    5564.087823    1.2174 secs    5465.781801    1.2414 secs 
  23   1934.889761    7.0861 secs    5476.220007    2.5224 secs    5548.504187    2.4744 secs    5465.500565    2.5118 secs 
  24   1939.683627    5.8652 secs    5461.486912    2.1110 secs    5548.744349    2.0488 secs    5417.722111    2.1042 secs 
  25   1925.342112   47.4712 secs    5476.818503   16.7678 secs    5557.570589   16.4377 secs    5479.097929   16.6700 secs 
  26   1930.362383   16.1728 secs    5486.557150    5.7494 secs    5553.792419    5.6187 secs    5544.780029    5.6293 secs 
  27   1945.269663    7.2153 secs    5443.169561    2.6035 secs    5534.059747    2.5462 secs    5507.743611    2.5530 secs 
  28   1920.384111   37.4526 secs    5479.914967   13.1715 secs    5553.680361   12.9380 secs    5507.436467   13.0454 secs 
  29   1940.307975    7.8315 secs    5530.787084    2.7661 secs    5547.749218    2.7347 secs    5510.767015    2.7558 secs 
  30   1927.658333    1.1905 mins    5468.604811   25.2139 secs    5438.685448   25.3136 secs    5555.456216   24.7841 secs 
  31   1942.378857   28.4496 secs    5520.634781   10.0240 secs    5501.207943   10.0433 secs    5510.264398   10.0245 secs 
  32   1904.831829   59.7541 secs    5521.457239   20.6445 secs    5537.529539   20.5532 secs    5496.131886   20.7084 secs

Standard OpenSSL library averaged 1897 hops per second
secp256k1 (S 8X32, F 10X26) averaged 5258 hops per second
secp256k1(S 4X64, F 5X52) averaged 5352 hops per second
secp256k1(S 4X64, F 5X52, , ENDOMORMPHSIM) averaged 5350 hops per second

We currently have ECMULT_WINDOW_SIZE set to 15. Does anyone know how changing this setting will affect performance?

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

One weird thing is that the runs on the Linux machine took longer than the ones on Windows (usually is the other way around). And the other weird thing is that the program is called 'roo' in Windows and 'ROO.exe' in Linux

It is actually ROO.exe in Windows but Windows adds the .exe for you and is not case sensitive.

Quote from: Telariust on August 24, 2019, 01:30:14 PM

Quote from: BurtW on August 24, 2019, 10:24:55 AM

..OpenSSL library is pretty slow.

...
ideally you need C bitcoin/secp256k1
...

Thanks for the suggestion! I should have thought of that first. It is silly to use OpenSSL for secp256k1 when there is a highly optimized specialized implementation available. Results available soon.

Telariust

jr. member

Activity: 38

Merit: 18

Quote from: BurtW on August 24, 2019, 10:24:55 AM

..OpenSSL library is pretty slow.

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?)

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

We are about to release the first executable of our project for feedback. There will be a Windows 64 bit cygwin version and a 64 bit Linux version. The program is written in C using the standard OpenSSL library BIGNUM and EC_POINT objects. The main thing we are interested in for this release of the program is the number of hops per second on various machines. It seems to us the OpenSSL library is pretty slow. Here is what three runs of the program, for a 35 bit key, looks like on my Windows laptop:

Code:

C:\ROO\Debug>roo

ver   = 121 with 128 bit integers
test  = 34
seed  = 1566657361 (randomly selected)
bits  = 35
a     = 0x400000000
b     = 0x7FFFFFFFF
P     = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba    = 0x3FFFFFFFF
k0000 = 0x9D8358B56E7B4401A459C0D828A75681
s     = 0x4AED21170
%     =   17.0723
s*G   = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time  =    9.0817 mins (544899402700 nsecs)
hps   = 1968.057310

C:\ROO\Debug>roo

ver   = 121 with 128 bit integers
test  = 34
seed  = 1566658074 (randomly selected)
bits  = 35
a     = 0x400000000
b     = 0x7FFFFFFFF
P     = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba    = 0x3FFFFFFFF
k0000 = 0xC7B9A08889DCE535759804A45AE046BC
s     = 0x4AED21170
%     =   17.0723
s*G   = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time  =    9.0295 mins (541767121800 nsecs)
hps   = 1986.290418

C:\ROO\Debug>roo

ver   = 121 with 128 bit integers
test  = 34
seed  = 1566658634 (randomly selected)
bits  = 35
a     = 0x400000000
b     = 0x7FFFFFFFF
P     = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba    = 0x3FFFFFFFF
k0000 = 0xDF1DD25825020380D574A71285072428
s     = 0x4AED21170
%     =   17.0723
s*G   = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time  =    9.0542 mins (543253475900 nsecs)
hps   = 1981.294420

C:\ROO\Debug>

And here are three runs on my Linux machine. Maybe I just need to buy a much faster computer.

Code:

burt@burt-MS-7640:~/ROO1/Debug$ ./ROO.exe

ver   = 121 with 128 bit integers
test  = 34
seed  = 1566661363 (randomly selected)
bits  = 35
a     = 0x400000000
b     = 0x7FFFFFFFF
P     = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba    = 0x3FFFFFFFF
k0000 = 0xE6A6C5C436EBA130AD726DC36B710275
s     = 0x4AED21170
%     =   17.0723
s*G   = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time  =   15.0364 mins (902182961776 nsecs)
hps   = 1225.428980

burt@burt-MS-7640:~/ROO1/Debug$ ./ROO.exe

ver   = 121 with 128 bit integers
test  = 34
seed  = 1566663911 (randomly selected)
bits  = 35
a     = 0x400000000
b     = 0x7FFFFFFFF
P     = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba    = 0x3FFFFFFFF
k0000 = 0x1970EBB70E07E6F19E9D0390432AD93C
s     = 0x4AED21170
%     =   17.0723
s*G   = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time  =   14.6529 mins (879173107944 nsecs)
hps   = 1219.290980

burt@burt-MS-7640:~/ROO1/Debug$ ./ROO.exe

ver   = 121 with 128 bit integers
test  = 34
seed  = 1566665966 (randomly selected)
bits  = 35
a     = 0x400000000
b     = 0x7FFFFFFFF
P     = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
ba    = 0x3FFFFFFFF
k0000 = 0x504A020DE4246A5FF39CD676B27DD5A3
s     = 0x4AED21170
%     =   17.0723
s*G   = 0x2F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D
time  =   14.7170 mins (883021823424 nsecs)
hps   = 1217.660480

burt@burt-MS-7640:~/ROO1/Debug$

Darmont33

newbie

Activity: 18

Merit: 0

Quote from: ?? on ??

Who need some code, I have it for Python 2.7!
This is my own code and I apologize for absolutely no-PEP. And for my English, I apologize too.
The code is not so fast, but my estimation is more optimistic - only 10000 years on average for the problem 105.
Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code.

The code is on my WebSite:
http://fe57.org/forum/thread.php?board=4&thema=1#1

This is my main interest. You are now informed that my site exists in the Universe!
To be more interesting: test problem 75 from pickachunakapika to drotika solution:
26970178626862821196031
(decimal)
I guess that the solution can be posted now because all deadlines are finished. Or I miss something and drotika was already posted the answer.

Very nice

For those who use python3, you may have to change a few things for the code to work:

1) for all print statements you need (), for example line 60
change this > print 'prime must be 3 modulo 4'
to this > print ('prime must be 3 modulo 4')

2) make sure you distinguish between integer division // and float division /
for example, line 63
change this > pw = (p + 1) / 4
to this > pw = (p + 1) // 4

For case 32 I get
P-table prepared
tame and wild herds are prepared
6091.198 h/s
6119.991 h/s
6047.619 h/s
6028.418 h/s
6020.816 h/s
5995.830 h/s
6041.220 h/s
6026.008 h/s
6077.185 h/s
total time: 45.38 sec
SOLVED: 3093472814
Hops: 273742
tame and wild herds are prepared
5995.223 h/s
6044.420 h/s
5966.429 h/s
6050.819 h/s
total time: 68.41 sec
SOLVED: 3093472814
Hops: 137749
tame and wild herds are prepared
6038.017 h/s
5968.435 h/s
total time: 82.83 sec
SOLVED: 3093472814
Hops: 85546
165679.0 +/- 56093.66357263537
Average time to solve: 27.61 sec

Hi, how did you change line 160 for python 3?

if you mean this line:

print '%.3f h/s'%((Hops-Hops_old)/(t1-t0))
just add parenthesis
print ('%.3f h/s'%((Hops-Hops_old)/(t1-t0)))
do the same for all print statements.

Now everything works!
I didn’t put it there ()
thank Wink

itod

legendary

Activity: 1974

Merit: 1077

^ Will code for Bitcoins

Quote from: ?? on ??

Have anyone experience to change the script for multi thread or cuda GPU? Also for uncompressed public keys?

It's not trivial to implement it in CUDA. Read here about the problems expected: https://github.com/beranm14/pollard_rho/blob/master/report/main.pdf

57fe

newbie

Activity: 8

Merit: 4

Quote from: ?? on ??

Quote from: 57fe on August 20, 2019, 12:11:03 PM

Anyway, the table with time-to-solve estimations posted by j2002ba2 means GPUs are 3..4-order more efficient than the code presented.
j2002ba2, if you are here, how many hops/sec you have reached on single Tesla V100? Is my estimation of 2 GHops/s correct? At least 1 GHops/s required if authomorphisms taken into account, but I can't beat even half of this value.

For me 4x Tesla V100 on AWS were running at 6515 Mj/s, this gives 1629 Mj/s for a single V100.

This is really cool! j2002ba2, thank you very much for posting this reference point.

57fe

newbie

Activity: 8

Merit: 4

Quote from: ?? on ??

Quote

If you wish to speed up calculations by a factor 15 approximately, install gmpy2 module..

that's great but

Quote

random.randint

this is a very slow function, try to speed up through its analog numpy.random

Functions from random module used only in preliminary stage for placement tame and wild herds. So, there is almost no influence on speed of the algorithm. Only if we try to select a huge number of kangaroos. Also, when the problem is very simple (16 bit, for example) the time of the placement may be significant in comparison with the time of solution. But total time still very small for human.
For pseudorandom hops the coordinate X itself is used.
Main goal of the code presented is a template with minimal dependencies. Numpy is external module which requires installation.
But I can't eliminate gmpy2 at all, it is very efficient.
Anyway, the table with time-to-solve estimations posted by j2002ba2 means GPUs are 3..4-order more efficient than the code presented.
j2002ba2, if you are here, how many hops/sec you have reached on single Tesla V100? Is my estimation of 2 GHops/s correct? At least 1 GHops/s required if authomorphisms taken into account, but I can't beat even half of this value.

vimp666

jr. member

Activity: 37

Merit: 1

Quote from: ?? on ??

Who need some code, I have it for Python 2.7!
This is my own code and I apologize for absolutely no-PEP. And for my English, I apologize too.
The code is not so fast, but my estimation is more optimistic - only 10000 years on average for the problem 105.
Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code.

The code is on my WebSite:
http://fe57.org/forum/thread.php?board=4&thema=1#1

This is my main interest. You are now informed that my site exists in the Universe!
To be more interesting: test problem 75 from pickachunakapika to drotika solution:
26970178626862821196031
(decimal)
I guess that the solution can be posted now because all deadlines are finished. Or I miss something and drotika was already posted the answer.

Very nice

For those who use python3, you may have to change a few things for the code to work:

1) for all print statements you need (), for example line 60
change this > print 'prime must be 3 modulo 4'
to this > print ('prime must be 3 modulo 4')

2) make sure you distinguish between integer division // and float division /
for example, line 63
change this > pw = (p + 1) / 4
to this > pw = (p + 1) // 4

For case 32 I get
P-table prepared
tame and wild herds are prepared
6091.198 h/s
6119.991 h/s
6047.619 h/s
6028.418 h/s
6020.816 h/s
5995.830 h/s
6041.220 h/s
6026.008 h/s
6077.185 h/s
total time: 45.38 sec
SOLVED: 3093472814
Hops: 273742
tame and wild herds are prepared
5995.223 h/s
6044.420 h/s
5966.429 h/s
6050.819 h/s
total time: 68.41 sec
SOLVED: 3093472814
Hops: 137749
tame and wild herds are prepared
6038.017 h/s
5968.435 h/s
total time: 82.83 sec
SOLVED: 3093472814
Hops: 85546
165679.0 +/- 56093.66357263537
Average time to solve: 27.61 sec

I think with gmpy2 it's a lot faster.I have 145,000h/s

Average time to solve: 0.86 sec

vimp666

jr. member

Activity: 37

Merit: 1

Quote from: ?? on ??

Quote from: vimp666 on August 20, 2019, 07:46:56 AM

X = X % (2**256) it turns out after this line you need to insert Y = Y % (2**256)?

No. First, you need coordinates of EC-point in uncompressed form. See, for example, the transaction:

https://www.blockchain.com/ru/btc/tx/69211d75f7aa8b2bd8f495a672de5cb87d5ce3789cfb0a91407a4b9120405384?show_adv=true

There is uncompressed coordinates in every record starting from words PUSHDATA(65). Let's take the one of them:

Code:

PUSHDATA(65)[0485c26293005c33a5afafada4fd3177767af371927db1c8519402d04072cf9852b3f555474c9cbac1f786141da4bad9fabb4e450dd812a7f1e69ca662caef1796]

You can split this hex number manually, or with Python:

Code:

s = '85c26293005c33a5afafada4fd3177767af371927db1c8519402d04072cf9852b3f555474c9cbac1f786141da4bad9fabb4e450dd812a7f1e69ca662caef1796'
XY = int(s, 16)
X = XY >> 256
Y = XY % (2**256)

Note, that starting two symbols 04 must be deleted, because this is only the flag-byte of uncompressed point coordinates.

Yes, I understand how to divide the public key into x and y points.I want to understand what needs to be added to the code before line 188?

vimp666

jr. member

Activity: 37

Merit: 1

Quote from: ?? on ??

Quote

Would be possible to work also with uncompressed addresses?

Yes, it's even simpler than for compressed address. All you need is to set X and Y coordinates from an uncompressed record explicitly just before line 188 in the code. No need to calculate Y from X. If I think correctly, uncompressed coordinates in blockchain definitely means uncompressed address. Perhaps, it is actual only for very old blocks.

X = X % (2**256) it turns out after this line need to insert Y = Y % (2**256)?or enter the coordinates in hex format?

supika

newbie

Activity: 43

Merit: 0

Quote from: ?? on ??

Who need some code, I have it for Python 2.7!
This is my own code and I apologize for absolutely no-PEP. And for my English, I apologize too.
The code is not so fast, but my estimation is more optimistic - only 10000 years on average for the problem 105.
Tests with C++ (VS2013) leads to x2..x3 faster calculations only (single-thread), but much more complicated code.

The code is on my WebSite:
http://fe57.org/forum/thread.php?board=4&thema=1#1

This is my main interest. You are now informed that my site exists in the Universe!
To be more interesting: test problem 75 from pickachunakapika to drotika solution:
26970178626862821196031
(decimal)
I guess that the solution can be posted now because all deadlines are finished. Or I miss something and drotika was already posted the answer.

Great contribution @57fe
The script is working only with compressed addresses?
Would be possible to work also with uncompressed addresses?

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

See chart: https://imgur.com/M8j5rdl

We are still fine tuning the algorithm. Using just one thread on a PC and an algorithm which uses almost no luck we predict it would take 101 million years to find #105. This is using a small number of very careful and "thorough" tame kangaroos. Next we will try to get better results using a larger number of more luck based tame kangaroos.

Data collected by the latest algorithm:

Code:

bits
====
   1    8.3905 milliseconds
   2   20.9155 milliseconds
   3   19.8591 milliseconds
   4   37.3427 milliseconds
   5   51.0067 milliseconds
   6   78.4731 milliseconds
   7   87.5237 milliseconds
   8  136.0477 milliseconds
   9  140.6669 milliseconds
  10  298.3345 milliseconds
  11  283.3537 milliseconds
  12  509.9002 milliseconds
  13  516.9761 milliseconds
  14    1.984  seconds
  15    2.1595 seconds
  16    2.0624 seconds
  17    2.1664 seconds
  18    4.261  seconds
  19    9.1044 seconds
  20   27.1053 seconds
  21   17.9858 seconds
  22   16.4732 seconds
  23   57.0384 seconds
  24    1.3351 minutes
  25    1.2272 minutes
  26    2.6514 minutes
  27    2.2304 minutes
  28    4.3598 minutes
  29    4.4495 minutes
  30    8.6276 minutes
  31   12.9661 minutes
  32   25.6822 minutes
  33   36.0675 minutes
  34    1.1545 hours
  35   51.3179 minutes
  36    1.7085 hours
  37    1.7121 hours
  38    4.5732 hours
  39    2.263  hours
  40    9.1259 hours

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

I would like to test your program.

Quote from: ?? on ??

I would like to test your program Kiss

Quote from: ?? on ??

If you need more testers i would like to participate and help out
I have been following the 100BTC challenge thread and just recently tried working with bitcrack

Quote from: ?? on ??

I would like to test your program, BurtW.

All added to the list in the OP

byyuans

brand new

Activity: 0

Merit: 0

@BurtW Maybe it'il help.

https://github.com/beranm14/pollard_rho/tree/master/cuda_v1

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

I would like to test your program. Grin

Quote from: Telariust on August 09, 2019, 01:29:16 AM

I would like to test your Pollard Kangaroo program.
(need more examples sources for undestand concept how it work. bin no interest. lang any.)

Quote from: ?? on ??

I would like to become a tester, but I have a very weak AMD laptop.

Quote from: ?? on ??

I would like to test your program. Roll Eyes

All added to the list in the OP.

Telariust

jr. member

Activity: 38

Merit: 18

Top useful links:

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

======

Sorry, I can not resist Grin

a little friendly trolling

Quote

Dad, for the new year, I asked Santa to give me Barbie and DVD with the new Winx Club season.
Why did he decide that the “Pollard Kangaroo Algorithm in raw asm” would be better?

======
I would like to test your Pollard Kangaroo program.
(need more examples sources for undestand concept how it work. bin no interest. lang any.)

Firebox

jr. member

Activity: 59

Merit: 3

Quote from: BurtW on August 08, 2019, 06:26:12 AM

Quote from: ?? on ??

BurtW
You give source code or binary file?

We have not decided yet on that. If you would trust me I can give you the executable much sooner. If you would not trust an executable from me then you would have to wait for us to decide to give out the source code.

We are still making great strides in making it faster so we are not ready to publish it as an executable or as source yet.

We are also waiting to see if drotika actually publishes their code and what it looks like when it is published.

BurtW,
You are, guys, doing a very comprehensive and very very important work. Such a tallented kids like your daughter deserves not only the awarded medal in the school but a huge popularity within the scientific comunity, as such kids are the ones who will definetely influence our future.

Personnaly me, I have no any reason to NOT trust your binaries. So if you will publish it I will definetely test it on my PC. Even if it will f**k up my machine I will have NO any complaints to you.

I wish you great success in all what you are doing!

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

This shows that luck is a major factor in the total run time. In general it should take about twice as much time to find the next key but the run times are all over the map because of the luck factor:

Code:

Bits in the   Number of tame   Time to find
private key   kangaroos used   the key (secs)
-----------   --------------   --------------
         33                1       270.912048
         34               15      7882.658203
         35                1      1026.184082
         36                3      5582.397949
         37                7     25962.619141
         38                3     22675.375000

We are still optimizing the code so the absolute values of these run time will go down over time as the program is improved.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

BurtW
You give source code or binary file?

We have not decided yet on that. If you would trust me I can give you the executable much sooner. If you would not trust an executable from me then you would have to wait for us to decide to give out the source code.

We are still making great strides in making it faster so we are not ready to publish it as an executable or as source yet.

We are also waiting to see if drotika actually publishes their code and what it looks like when it is published.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

Yes and no. One of the bits in your private keys is always 1, so it can't count toward entropy. If your range goes from 0x20 to 0x3f, then there are 32 possible values, so 5 bits of entropy. If it goes to 0x40, then there are 33 possible values and slightly more than 5 bits.

Also, what I know about the algorithm is what I got from skimming the wikipedia article. A couple questions:

1. Is there a reason for not setting a to 0?
2. What is your mapping function?

OK, we will fix the terminology issue. bits = the number of bits in the private key, not the entropy (which is one less).

There are two conditions that can happen when you run the wild kangaroo portion of the algorithm: there is a collision with the tame kangaroo and the private key is found, or, the two fail to collide. The termination condition for a failure to collide is test (b - a + c) so if a is zero then it will cause the algorithm to run longer than necessary in the failure to collide case.

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

Quote from: BurtW on August 07, 2019, 12:00:27 PM

bits = number of BITS of entropy in the private key
a = lower bound for the private key search
b = upper bound for the private key search

I think your number of bits of entropy value is off by one, unless bounds are inclusive and you are rounding up.

Thanks for the feedback.

Here is an example from the output:

Code:

test  = 5
bits  = 6
a     = 0x20
b     = 0x40

The first private key that has 6 bits is 0x20, the last one that has 6 bits would be 0x3F. So, yes, I need to subtract one from the value of b being displayed.

Is that what you are referring to?

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

just make a volcano like everyone else she will get a good grade on the project. It looks cool to and she will have fun. Grin

Combine the vinegar, water, dish soap and 2 drops of food coloring into the empty soda bottle. Use a spoon to mix the baking soda slurry until it is all a liquid. Eruption time! … Pour the baking soda slurry into the soda bottle quickly and step back!

She actually did that for here kindergarten science fair project.

Here is a list of the 2018 Colorado Science & Engineering Fair entries. Take a look at the titles of the projects. This will give you some idea of the quality of the projects she is competing against:

http://www.csef.colostate.edu/2018CSEF/2018_Finalists.html

You will see that there is not a single vinegar and baking soda volcano in the entire list Wink

BurtW

legendary

Activity: 2646

Merit: 1137

All paid signature campaigns should be banned.

Quote from: ?? on ??

Please note that since this thread will be used as reference material in a science fair project we delete most posts in this thread just to keep it clean.

In other words, once we quote a post and answer it then we delete the original post.

Your post and the answers we gave or questions from us will all still be in the thread.

The thread stays shorter and cleaner this way.

I hope this is not an issue for anyone. It is just to keep the thread as short and clean as possible. It is not because we do not appreciate your posts.

We do!

Thanks!

My middle school daughter and I are working together on a science fair project related to using the Pollard Kangaroo algorithm to find low entropy private keys when the public key is known.

So far we have written the basic code and it works. We are using the results from the "Private Key Entropy Test Transactions" (best thread here) (other thread here) as our known answer unit test for the program.

Found a lot of good information here

The current "record" for the largest private keys found by the program is shown below. Note how slow the program is compared to the state of the art GPU based programs:

Code:

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 56
seed  = none (default value)
b     = 2 ^ 57 = 0x0200000000000000
a     = 2 ^ 56 = 0x0100000000000000
P     = 0x02A521A07E98F78B03FC1E039BC3A51408CD73119B5EB116E583FE57DC8DB07AEA (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x01EB25C90795D61C
s*G   = 0x02A521A07E98F78B03FC1E039BC3A51408CD73119B5EB116E583FE57DC8DB07AEA (33 bytes)
numt  = 0x8 (8)
mem   = 0x4BE00 (310784) bytes
cmps  = 0x34C9808B (885620875)
hops  = 0x39144058 (957628504)
hps   = 153790.653757
time  =    1.7297 hours (6226831609100 nsecs)

The unit test results from the latest version of the code, version 186. The unit test consists of running the program 57 times to find the private keys which contain from 1 bit to 57 bits:

Code:

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 0
seed  = none (default value)
b     = 2 ^  1 = 0x02
a     = 2 ^  0 = 0x01
P     = 0x0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x01
s*G   = 0x0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0x3 (3)
hops  = 0x1 (1)
hps   = 1167.678655
time  =    0.8564 msecs (856400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 1
seed  = none (default value)
b     = 2 ^  2 = 0x04
a     = 2 ^  1 = 0x02
P     = 0x02F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x03
s*G   = 0x02F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9 (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0x3 (3)
hops  = 0x1 (1)
hps   = 1337.077149
time  =    0.7479 msecs (747900 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 2
seed  = none (default value)
b     = 2 ^  3 = 0x08
a     = 2 ^  2 = 0x04
P     = 0x025CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x07
s*G   = 0x025CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0x3 (3)
hops  = 0x1 (1)
hps   = 1632.120124
time  =    0.6127 msecs (612700 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 3
seed  = none (default value)
b     = 2 ^  4 = 0x10
a     = 2 ^  3 = 0x08
P     = 0x022F01E5E15CCA351DAFF3843FB70F3C2F0A1BDD05E5AF888A67784EF3E10A2A01 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x08
s*G   = 0x022F01E5E15CCA351DAFF3843FB70F3C2F0A1BDD05E5AF888A67784EF3E10A2A01 (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0xA (10)
hops  = 0x8 (8)
hps   = 925.443924
time  =    8.6445 msecs (8644500 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 4
seed  = none (default value)
b     = 2 ^  5 = 0x20
a     = 2 ^  4 = 0x10
P     = 0x02352BBF4A4CDD12564F93FA332CE333301D9AD40271F8107181340AEF25BE59D5 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x15
s*G   = 0x02352BBF4A4CDD12564F93FA332CE333301D9AD40271F8107181340AEF25BE59D5 (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0xD (13)
hops  = 0xB (11)
hps   = 6757.171816
time  =    1.6279 msecs (1627900 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 5
seed  = none (default value)
b     = 2 ^  6 = 0x40
a     = 2 ^  5 = 0x20
P     = 0x03F2DAC991CC4CE4B9EA44887E5C7C0BCE58C80074AB9D4DBAEB28531B7739F530 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x31
s*G   = 0x03F2DAC991CC4CE4B9EA44887E5C7C0BCE58C80074AB9D4DBAEB28531B7739F530 (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0x11 (17)
hops  = 0xF (15)
hps   = 7703.368940
time  =    1.9472 msecs (1947200 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 6
seed  = none (default value)
b     = 2 ^  7 = 0x80
a     = 2 ^  6 = 0x40
P     = 0x0296516A8F65774275278D0D7420A88DF0AC44BD64C7BAE07C3FE397C5B3300B23 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x4C
s*G   = 0x0296516A8F65774275278D0D7420A88DF0AC44BD64C7BAE07C3FE397C5B3300B23 (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0x36 (54)
hops  = 0x34 (52)
hps   = 4226.886248
time  =   12.3022 msecs (12302200 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 7
seed  = none (default value)
b     = 2 ^  8 = 0x0100
a     = 2 ^  7 = 0x80
P     = 0x0308BC89C2F919ED158885C35600844D49890905C79B357322609C45706CE6B514 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0xE0
s*G   = 0x0308BC89C2F919ED158885C35600844D49890905C79B357322609C45706CE6B514 (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0x22 (34)
hops  = 0x20 (32)
hps   = 15992.803239
time  =    2.0009 msecs (2000900 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 8
seed  = none (default value)
b     = 2 ^  9 = 0x0200
a     = 2 ^  8 = 0x0100
P     = 0x0243601D61C836387485E9514AB5C8924DD2CFD466AF34AC95002727E1659D60F7 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x01D3
s*G   = 0x0243601D61C836387485E9514AB5C8924DD2CFD466AF34AC95002727E1659D60F7 (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0x2F (47)
hops  = 0x2D (45)
hps   = 13742.136444
time  =    3.2746 msecs (3274600 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 9
seed  = none (default value)
b     = 2 ^ 10 = 0x0400
a     = 2 ^  9 = 0x0200
P     = 0x03A7A4C30291AC1DB24B4AB00C442AA832F7794B5A0959BEC6E8D7FEE802289DCD (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x0202
s*G   = 0x03A7A4C30291AC1DB24B4AB00C442AA832F7794B5A0959BEC6E8D7FEE802289DCD (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0x200 (512)
hops  = 0x1FE (510)
hps   = 47568.414573
time  =   10.7214 msecs (10721400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 10
seed  = none (default value)
b     = 2 ^ 11 = 0x0800
a     = 2 ^ 10 = 0x0400
P     = 0x038B05B0603ABD75B0C57489E451F811E1AFE54A8715045CDF4888333F3EBC6E8B (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x0483
s*G   = 0x038B05B0603ABD75B0C57489E451F811E1AFE54A8715045CDF4888333F3EBC6E8B (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0x37F (895)
hops  = 0x37D (893)
hps   = 48783.419100
time  =   18.3054 msecs (18305400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 11
seed  = none (default value)
b     = 2 ^ 12 = 0x1000
a     = 2 ^ 11 = 0x0800
P     = 0x038B00FCBFC1A203F44BF123FC7F4C91C10A85C8EAE9187F9D22242B4600CE781C (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x0A7B
s*G   = 0x038B00FCBFC1A203F44BF123FC7F4C91C10A85C8EAE9187F9D22242B4600CE781C (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0x587 (1415)
hops  = 0x585 (1413)
hps   = 53594.796033
time  =   26.3645 msecs (26364500 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 12
seed  = none (default value)
b     = 2 ^ 13 = 0x2000
a     = 2 ^ 12 = 0x1000
P     = 0x03AADAAAB1DB8D5D450B511789C37E7CFEB0EB8B3E61A57A34166C5EDC9A4B869D (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x1460
s*G   = 0x03AADAAAB1DB8D5D450B511789C37E7CFEB0EB8B3E61A57A34166C5EDC9A4B869D (33 bytes)
numt  = 0x1 (1)
mem   = 0x4D0 (1232) bytes
cmps  = 0xBA2 (2978)
hops  = 0xBA0 (2976)
hps   = 37949.163932
time  =   78.4207 msecs (78420700 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 13
seed  = none (default value)
b     = 2 ^ 14 = 0x4000
a     = 2 ^ 13 = 0x2000
P     = 0x03B4F1DE58B8B41AFE9FD4E5FFBDAFAEAB86C5DB4769C15D6E6011AE7351E54759 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x2930
s*G   = 0x03B4F1DE58B8B41AFE9FD4E5FFBDAFAEAB86C5DB4769C15D6E6011AE7351E54759 (33 bytes)
numt  = 0x8 (8)
mem   = 0x5580 (21888) bytes
cmps  = 0x152 (338)
hops  = 0x346 (838)
hps   = 61841.823670
time  =   13.5507 msecs (13550700 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 14
seed  = none (default value)
b     = 2 ^ 15 = 0x8000
a     = 2 ^ 14 = 0x4000
P     = 0x02FEA58FFCF49566F6E9E9350CF5BCA2861312F422966E8DB16094BEB14DC3DF2C (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x68F3
s*G   = 0x02FEA58FFCF49566F6E9E9350CF5BCA2861312F422966E8DB16094BEB14DC3DF2C (33 bytes)
numt  = 0x8 (8)
mem   = 0x5B40 (23360) bytes
cmps  = 0x26 (38)
hops  = 0x2BE (702)
hps   = 45441.893283
time  =   15.4483 msecs (15448300 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 15
seed  = none (default value)
b     = 2 ^ 16 = 0x010000
a     = 2 ^ 15 = 0x8000
P     = 0x029D8C5D35231D75EB87FD2C5F05F65281ED9573DC41853288C62EE94EB2590B7A (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0xC936
s*G   = 0x029D8C5D35231D75EB87FD2C5F05F65281ED9573DC41853288C62EE94EB2590B7A (33 bytes)
numt  = 0x8 (8)
mem   = 0x66C0 (26304) bytes
cmps  = 0x8F (143)
hops  = 0x43D (1085)
hps   = 48378.107234
time  =   22.4275 msecs (22427500 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 16
seed  = none (default value)
b     = 2 ^ 17 = 0x020000
a     = 2 ^ 16 = 0x010000
P     = 0x033F688BAE8321B8E02B7E6C0A55C2515FB25AB97D85FDA842449F7BFA04E128C3 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x01764F
s*G   = 0x033F688BAE8321B8E02B7E6C0A55C2515FB25AB97D85FDA842449F7BFA04E128C3 (33 bytes)
numt  = 0x8 (8)
mem   = 0x7DC0 (32192) bytes
cmps  = 0x131 (305)
hops  = 0x393 (915)
hps   = 36355.834217
time  =   25.1679 msecs (25167900 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 17
seed  = none (default value)
b     = 2 ^ 18 = 0x040000
a     = 2 ^ 17 = 0x020000
P     = 0x020CE4A3291B19D2E1A7BF73EE87D30A6BDBC72B20771E7DFFF40D0DB755CD4AF1 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x03080D
s*G   = 0x020CE4A3291B19D2E1A7BF73EE87D30A6BDBC72B20771E7DFFF40D0DB755CD4AF1 (33 bytes)
numt  = 0x8 (8)
mem   = 0xABC0 (43968) bytes
cmps  = 0x8D (141)
hops  = 0x2EB (747)
hps   = 24050.380234
time  =   31.0598 msecs (31059800 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 18
seed  = none (default value)
b     = 2 ^ 19 = 0x080000
a     = 2 ^ 18 = 0x040000
P     = 0x0385663C8B2F90659E1CCAB201694F4F8EC24B3749CFE5030C7C3646A709408E19 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x05749F
s*G   = 0x0385663C8B2F90659E1CCAB201694F4F8EC24B3749CFE5030C7C3646A709408E19 (33 bytes)
numt  = 0x8 (8)
mem   = 0x107C0 (67520) bytes
cmps  = 0x854 (2132)
hops  = 0xA91 (2705)
hps   = 60975.884658
time  =   44.3618 msecs (44361800 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 19
seed  = none (default value)
b     = 2 ^ 20 = 0x100000
a     = 2 ^ 19 = 0x080000
P     = 0x033C4A45CBD643FF97D77F41EA37E843648D50FD894B864B0D52FEBC62F6454F7C (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x0D2C55
s*G   = 0x033C4A45CBD643FF97D77F41EA37E843648D50FD894B864B0D52FEBC62F6454F7C (33 bytes)
numt  = 0x8 (8)
mem   = 0x1BFC0 (114624) bytes
cmps  = 0x3B5 (949)
hops  = 0x5EB (1515)
hps   = 23866.874826
time  =   63.4771 msecs (63477100 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 20
seed  = none (default value)
b     = 2 ^ 21 = 0x200000
a     = 2 ^ 20 = 0x100000
P     = 0x031A746C78F72754E0BE046186DF8A20CDCE5C79B2EDA76013C647AF08D306E49E (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x1BA534
s*G   = 0x031A746C78F72754E0BE046186DF8A20CDCE5C79B2EDA76013C647AF08D306E49E (33 bytes)
numt  = 0x8 (8)
mem   = 0x32FC0 (208832) bytes
cmps  = 0xC38 (3128)
hops  = 0xF07 (3847)
hps   = 32010.291221
time  =  120.1801 msecs (120180100 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 21
seed  = none (default value)
b     = 2 ^ 22 = 0x400000
a     = 2 ^ 21 = 0x200000
P     = 0x023ED96B524DB5FF4FE007CE730366052B7C511DC566227D929070B9CE917ABB43 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x2DE40F
s*G   = 0x023ED96B524DB5FF4FE007CE730366052B7C511DC566227D929070B9CE917ABB43 (33 bytes)
numt  = 0x8 (8)
mem   = 0x60FC0 (397248) bytes
cmps  = 0x1419 (5145)
hops  = 0x1501 (5377)
hps   = 26854.198235
time  =  200.2294 msecs (200229400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 22
seed  = none (default value)
b     = 2 ^ 23 = 0x800000
a     = 2 ^ 22 = 0x400000
P     = 0x03F82710361B8B81BDEDB16994F30C80DB522450A93E8E87EEB07F7903CF28D04B (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x556E52
s*G   = 0x03F82710361B8B81BDEDB16994F30C80DB522450A93E8E87EEB07F7903CF28D04B (33 bytes)
numt  = 0x8 (8)
mem   = 0xBCFC0 (774080) bytes
cmps  = 0x2DDC (11740)
hops  = 0x2FE2 (12258)
hps   = 30810.188827
time  =  397.8554 msecs (397855400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 23
seed  = none (default value)
b     = 2 ^ 24 = 0x01000000
a     = 2 ^ 23 = 0x800000
P     = 0x036EA839D22847EE1DCE3BFC5B11F6CF785B0682DB58C35B63D1342EB221C3490C (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0xDC2A04
s*G   = 0x036EA839D22847EE1DCE3BFC5B11F6CF785B0682DB58C35B63D1342EB221C3490C (33 bytes)
numt  = 0x8 (8)
mem   = 0x9FC0 (40896) bytes
cmps  = 0x169C (5788)
hops  = 0x22FD (8957)
hps   = 97635.683842
time  =   91.7390 msecs (91739000 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 24
seed  = none (default value)
b     = 2 ^ 25 = 0x02000000
a     = 2 ^ 24 = 0x01000000
P     = 0x03057FBEA3A2623382628DDE556B2A0698E32428D3CD225F3BD034DCA82DD7455A (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x01FA5EE5
s*G   = 0x03057FBEA3A2623382628DDE556B2A0698E32428D3CD225F3BD034DCA82DD7455A (33 bytes)
numt  = 0x8 (8)
mem   = 0xA580 (42368) bytes
cmps  = 0x302 (770)
hops  = 0xF5F (3935)
hps   = 60897.758313
time  =   64.6165 msecs (64616500 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 25
seed  = none (default value)
b     = 2 ^ 26 = 0x04000000
a     = 2 ^ 25 = 0x02000000
P     = 0x024E4F50A2A3ECCDB368988AE37CD4B611697B26B29696E42E06D71368B4F3840F (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x0340326E
s*G   = 0x024E4F50A2A3ECCDB368988AE37CD4B611697B26B29696E42E06D71368B4F3840F (33 bytes)
numt  = 0x8 (8)
mem   = 0xB100 (45312) bytes
cmps  = 0x2757 (10071)
hops  = 0x378E (14222)
hps   = 108573.670847
time  =  130.9894 msecs (130989400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 26
seed  = none (default value)
b     = 2 ^ 27 = 0x08000000
a     = 2 ^ 26 = 0x04000000
P     = 0x031A864BAE3922F351F1B57CFDD827C25B7E093CB9C88A72C1CD893D9F90F44ECE (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x06AC3875
s*G   = 0x031A864BAE3922F351F1B57CFDD827C25B7E093CB9C88A72C1CD893D9F90F44ECE (33 bytes)
numt  = 0x8 (8)
mem   = 0xC800 (51200) bytes
cmps  = 0x1B36 (6966)
hops  = 0x2601 (9729)
hps   = 92489.780397
time  =  105.1900 msecs (105190000 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 27
seed  = none (default value)
b     = 2 ^ 28 = 0x10000000
a     = 2 ^ 27 = 0x08000000
P     = 0x03E9E661838A96A65331637E2A3E948DC0756E5009E7CB5C36664D9B72DD18C0A7 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x0D916CE8
s*G   = 0x03E9E661838A96A65331637E2A3E948DC0756E5009E7CB5C36664D9B72DD18C0A7 (33 bytes)
numt  = 0x8 (8)
mem   = 0xF600 (62976) bytes
cmps  = 0x3684 (13956)
hops  = 0x44F2 (17650)
hps   = 115979.245957
time  =  152.1824 msecs (152182400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 28
seed  = none (default value)
b     = 2 ^ 29 = 0x20000000
a     = 2 ^ 28 = 0x10000000
P     = 0x026CAAD634382D34691E3BEF43ED4A124D8909A8A3362F91F1D20ABAAF7E917B36 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x17E2551E
s*G   = 0x026CAAD634382D34691E3BEF43ED4A124D8909A8A3362F91F1D20ABAAF7E917B36 (33 bytes)
numt  = 0x8 (8)
mem   = 0x15200 (86528) bytes
cmps  = 0x11D3 (4563)
hops  = 0x1EF0 (7920)
hps   = 76613.379095
time  =  103.3762 msecs (103376200 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 29
seed  = none (default value)
b     = 2 ^ 30 = 0x40000000
a     = 2 ^ 29 = 0x20000000
P     = 0x030D282CF2FF536D2C42F105D0B8588821A915DC3F9A05BD98BB23AF67A2E92A5B (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x3D94CD64
s*G   = 0x030D282CF2FF536D2C42F105D0B8588821A915DC3F9A05BD98BB23AF67A2E92A5B (33 bytes)
numt  = 0x8 (8)
mem   = 0x20A00 (133632) bytes
cmps  = 0x3BEFE (245502)
hops  = 0x3D2C4 (250564)
hps   = 190967.538171
time  =    1.3121 secs  (1312076400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 30
seed  = none (default value)
b     = 2 ^ 31 = 0x80000000
a     = 2 ^ 30 = 0x40000000
P     = 0x0387DC70DB1806CD9A9A76637412EC11DD998BE666584849B3185F7F9313C8FD28 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x7D4FE747
s*G   = 0x0387DC70DB1806CD9A9A76637412EC11DD998BE666584849B3185F7F9313C8FD28 (33 bytes)
numt  = 0x8 (8)
mem   = 0x37A00 (227840) bytes
cmps  = 0x23D68 (146792)
hops  = 0x24D86 (150918)
hps   = 175329.717642
time  =  860.7668 msecs (860766800 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 31
seed  = none (default value)
b     = 2 ^ 32 = 0x0100000000
a     = 2 ^ 31 = 0x80000000
P     = 0x0209C58240E50E3BA3F833C82655E8725C037A2294E14CF5D73A5DF8D56159DE69 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0xB862A62E
s*G   = 0x0209C58240E50E3BA3F833C82655E8725C037A2294E14CF5D73A5DF8D56159DE69 (33 bytes)
numt  = 0x8 (8)
mem   = 0x65A00 (416256) bytes
cmps  = 0x13DDFB (1302011)
hops  = 0x1407D6 (1312726)
hps   = 194092.676405
time  =    6.7634 secs  (6763397900 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 32
seed  = none (default value)
b     = 2 ^ 33 = 0x0200000000
a     = 2 ^ 32 = 0x0100000000
P     = 0x03A355AA5E2E09DD44BB46A4722E9336E9E3EE4EE4E7B7A0CF5785B283BF2AB579 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x01A96CA8D8
s*G   = 0x03A355AA5E2E09DD44BB46A4722E9336E9E3EE4EE4E7B7A0CF5785B283BF2AB579 (33 bytes)
numt  = 0x8 (8)
mem   = 0xC1A00 (793088) bytes
cmps  = 0x184BA6 (1592230)
hops  = 0x187FCE (1605582)
hps   = 195437.098767
time  =    8.2153 secs  (8215338900 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 33
seed  = none (default value)
b     = 2 ^ 34 = 0x0400000000
a     = 2 ^ 33 = 0x0200000000
P     = 0x033CDD9D6D97CBFE7C26F902FAF6A435780FE652E159EC953650EC7B1004082790 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x034A65911D
s*G   = 0x033CDD9D6D97CBFE7C26F902FAF6A435780FE652E159EC953650EC7B1004082790 (33 bytes)
numt  = 0x8 (8)
mem   = 0x13200 (78336) bytes
cmps  = 0x43797 (276375)
hops  = 0x544E2 (345314)
hps   = 136228.949723
time  =    2.5348 secs  (2534806300 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 34
seed  = none (default value)
b     = 2 ^ 35 = 0x0800000000
a     = 2 ^ 34 = 0x0400000000
P     = 0x02F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x04AED21170
s*G   = 0x02F6A8148A62320E149CB15C544FE8A25AB483A0095D2280D03B8A00A7FEADA13D (33 bytes)
numt  = 0x8 (8)
mem   = 0x137C0 (79808) bytes
cmps  = 0x2021 (8225)
hops  = 0x13156 (78166)
hps   = 62445.531121
time  =    1.2517 secs  (1251746900 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 35
seed  = none (default value)
b     = 2 ^ 36 = 0x1000000000
a     = 2 ^ 35 = 0x0800000000
P     = 0x02B3E772216695845FA9DDA419FB5DACA28154D8AA59EA302F05E916635E47B9F6 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x09DE820A7C
s*G   = 0x02B3E772216695845FA9DDA419FB5DACA28154D8AA59EA302F05E916635E47B9F6 (33 bytes)
numt  = 0x8 (8)
mem   = 0x14340 (82752) bytes
cmps  = 0xA83FE (689150)
hops  = 0xB992D (760109)
hps   = 163879.391715
time  =    4.6382 secs  (4638222000 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 36
seed  = none (default value)
b     = 2 ^ 37 = 0x2000000000
a     = 2 ^ 36 = 0x1000000000
P     = 0x027D2C03C3EF0AEC70F2C7E1E75454A5DFDD0E1ADEA670C1B3A4643C48AD0F1255 (33 bytes)
k0000 = 0x2DCF462904B478D8
k0001 = 0x68A7FF3F2BF1FCD9
s     = 0x1757756A93
s*G   = 0x027D2C03C3EF0AEC70F2C7E1E75454A5DFDD0E1ADEA670C1B3A4643C48AD0F1255 (33 bytes)
numt  = 0x8 (8)
mem   = 0x15C40 (89152) bytes
cmps  = 0x6AA0A9 (6987945)
hops  = 0x6D2105 (7151877)
hps   = 187772.773393
time  =   38.0879 secs  (38087934000 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 37
seed  = none (default value)
b     = 2 ^ 38 = 0x4000000000
a     = 2 ^ 37 = 0x2000000000
P     = 0x03C060E1E3771CBECCB38E119C2414702F3F5181A89652538851D2E3886BDD70C6 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x22382FACD0
s*G   = 0x03C060E1E3771CBECCB38E119C2414702F3F5181A89652538851D2E3886BDD70C6 (33 bytes)
numt  = 0x8 (8)
mem   = 0x18840 (100416) bytes
cmps  = 0x326522 (3302690)
hops  = 0x33AD16 (3386646)
hps   = 182235.685408
time  =   18.5839 secs  (18583879400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 38
seed  = none (default value)
b     = 2 ^ 39 = 0x8000000000
a     = 2 ^ 38 = 0x4000000000
P     = 0x022D77CD1467019A6BF28F7375D0949CE30E6B5815C2758B98A74C2700BC006543 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x4B5F8303E9
s*G   = 0x022D77CD1467019A6BF28F7375D0949CE30E6B5815C2758B98A74C2700BC006543 (33 bytes)
numt  = 0x8 (8)
mem   = 0x1E440 (123968) bytes
cmps  = 0x462142 (4596034)
hops  = 0x47824B (4686411)
hps   = 183080.898076
time  =   25.5975 secs  (25597487500 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 39
seed  = none (default value)
b     = 2 ^ 40 = 0x010000000000
a     = 2 ^ 39 = 0x8000000000
P     = 0x03A2EFA402FD5268400C77C20E574BA86409EDEDEE7C4020E4B9F0EDBEE53DE0D4 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0xE9AE4933D6
s*G   = 0x03A2EFA402FD5268400C77C20E574BA86409EDEDEE7C4020E4B9F0EDBEE53DE0D4 (33 bytes)
numt  = 0x8 (8)
mem   = 0x29C40 (171072) bytes
cmps  = 0x814EB5 (8474293)
hops  = 0x72B2DE (7516894)
hps   = 160988.917056
time  =   46.6920 secs  (46691996800 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 40
seed  = none (default value)
b     = 2 ^ 41 = 0x020000000000
a     = 2 ^ 40 = 0x010000000000
P     = 0x03B357E68437DA273DCF995A474A524439FAAD86FC9EFFC300183F714B0903468B (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x0153869ACC5B
s*G   = 0x03B357E68437DA273DCF995A474A524439FAAD86FC9EFFC300183F714B0903468B (33 bytes)
numt  = 0x8 (8)
mem   = 0x40C40 (265280) bytes
cmps  = 0x18135 (98613)
hops  = 0x28F92 (167826)
hps   = 95305.543521
time  =    1.7609 secs  (1760925900 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 41
seed  = none (default value)
b     = 2 ^ 42 = 0x040000000000
a     = 2 ^ 41 = 0x020000000000
P     = 0x03EEC88385BE9DA803A0D6579798D977A5D0C7F80917DAB49CB73C9E3927142CB6 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x02A221C58D8F
s*G   = 0x03EEC88385BE9DA803A0D6579798D977A5D0C7F80917DAB49CB73C9E3927142CB6 (33 bytes)
numt  = 0x8 (8)
mem   = 0x6EC40 (453696) bytes
cmps  = 0x26347AB (40060843)
hops  = 0x21C092F (35391791)
hps   = 163432.918870
time  =    3.6092 mins  (216552401100 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 42
seed  = none (default value)
b     = 2 ^ 43 = 0x080000000000
a     = 2 ^ 42 = 0x040000000000
P     = 0x02A631F9BA0F28511614904DF80D7F97A4F43F02249C8909DAC92276CCF0BCDAED (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x06BD3B27C591
s*G   = 0x02A631F9BA0F28511614904DF80D7F97A4F43F02249C8909DAC92276CCF0BCDAED (33 bytes)
numt  = 0x8 (8)
mem   = 0xCAC40 (830528) bytes
cmps  = 0xEE15186 (249647494)
hops  = 0xEEF75A3 (250574243)
hps   = 181027.446695
time  =   23.0696 mins  (1384178187200 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 43
seed  = none (default value)
b     = 2 ^ 44 = 0x100000000000
a     = 2 ^ 43 = 0x080000000000
P     = 0x025E466E97ED0E7910D3D90CEB0332DF48DDF67D456B9E7303B50A3D89DE357336 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x0E02B35A358F
s*G   = 0x025E466E97ED0E7910D3D90CEB0332DF48DDF67D456B9E7303B50A3D89DE357336 (33 bytes)
numt  = 0x8 (8)
mem   = 0x253E0 (152544) bytes
cmps  = 0x45511C (4542748)
hops  = 0x65AF2A (6663978)
hps   = 113200.466316
time  =   58.8688 secs  (58868821100 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 44
seed  = none (default value)
b     = 2 ^ 45 = 0x200000000000
a     = 2 ^ 44 = 0x100000000000
P     = 0x026ECABD2D22FDB737BE21975CE9A694E108EB94F3649C586CC7461C8ABF5DA71A (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x122FCA143C05
s*G   = 0x026ECABD2D22FDB737BE21975CE9A694E108EB94F3649C586CC7461C8ABF5DA71A (33 bytes)
numt  = 0x8 (8)
mem   = 0x259A0 (154016) bytes
cmps  = 0xDB72EF (14381807)
hops  = 0xFC9832 (16554034)
hps   = 148273.059015
time  =    1.8608 mins  (111645595700 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 45
seed  = none (default value)
b     = 2 ^ 46 = 0x400000000000
a     = 2 ^ 45 = 0x200000000000
P     = 0x03FD5487722D2576CB6D7081426B66A3E2986C1CE8358D479063FB5F2BB6DD5849 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x2EC18388D544
s*G   = 0x03FD5487722D2576CB6D7081426B66A3E2986C1CE8358D479063FB5F2BB6DD5849 (33 bytes)
numt  = 0x8 (8)
mem   = 0x26520 (156960) bytes
cmps  = 0x119F8DF (18479327)
hops  = 0x13BAE5B (20688475)
hps   = 154316.344166
time  =    2.2344 mins  (134065352000 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 46
seed  = none (default value)
b     = 2 ^ 47 = 0x800000000000
a     = 2 ^ 46 = 0x400000000000
P     = 0x023A12BD3CAF0B0F77BF4EEA8E7A40DBE27932BF80B19AC72F5F5A64925A594196 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x6CD610B53CBA
s*G   = 0x023A12BD3CAF0B0F77BF4EEA8E7A40DBE27932BF80B19AC72F5F5A64925A594196 (33 bytes)
numt  = 0x8 (8)
mem   = 0x27C20 (162848) bytes
cmps  = 0x1E74E4 (1996004)
hops  = 0x3AE4E1 (3859681)
hps   = 83000.365225
time  =   46.5020 secs  (46501976100 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 47
seed  = none (default value)
b     = 2 ^ 48 = 0x01000000000000
a     = 2 ^ 47 = 0x800000000000
P     = 0x0291BEE5CF4B14C291C650732FAA166040E4C18A14731F9A930C1E87D3EC12DEBB (33 bytes)
k0000 = 0x2DCF462904B478D8
k0001 = 0x68A7FF3F2BF1FCD9
s     = 0xADE6D7CE3B9B
s*G   = 0x0291BEE5CF4B14C291C650732FAA166040E4C18A14731F9A930C1E87D3EC12DEBB (33 bytes)
numt  = 0x8 (8)
mem   = 0x2AC20 (175136) bytes
cmps  = 0x1E1F1EFA (505356026)
hops  = 0x1E982AC6 (513288902)
hps   = 176154.639028
time  =   48.5642 mins  (2913854013900 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 48
seed  = none (default value)
b     = 2 ^ 49 = 0x02000000000000
a     = 2 ^ 48 = 0x01000000000000
P     = 0x02591D682C3DA4A2A698633BF5751738B67C343285EBDC3492645CB44658911484 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x0174176B015F4D
s*G   = 0x02591D682C3DA4A2A698633BF5751738B67C343285EBDC3492645CB44658911484 (33 bytes)
numt  = 0x8 (8)
mem   = 0x30620 (198176) bytes
cmps  = 0xA8440D4 (176439508)
hops  = 0xABE8B80 (180259712)
hps   = 174174.276996
time  =   17.2490 mins  (1034938770000 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 49
seed  = none (default value)
b     = 2 ^ 50 = 0x04000000000000
a     = 2 ^ 49 = 0x02000000000000
P     = 0x03F46F41027BBF44FAFD6B059091B900DAD41E6845B2241DC3254C7CDD3C5A16C6 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x022BD43C2E9354
s*G   = 0x03F46F41027BBF44FAFD6B059091B900DAD41E6845B2241DC3254C7CDD3C5A16C6 (33 bytes)
numt  = 0x8 (8)
mem   = 0x3BE20 (245280) bytes
cmps  = 0xE6FCB63 (242207587)
hops  = 0xEAE1EB5 (246292149)
hps   = 175194.304007
time  =   23.4304 mins  (1405822811400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 50
seed  = none (default value)
b     = 2 ^ 51 = 0x08000000000000
a     = 2 ^ 50 = 0x04000000000000
P     = 0x028C6C67BEF9E9EEBE6A513272E50C230F0F91ED560C37BC9B033241FF6C3BE78F (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x075070A1A009D4
s*G   = 0x028C6C67BEF9E9EEBE6A513272E50C230F0F91ED560C37BC9B033241FF6C3BE78F (33 bytes)
numt  = 0x8 (8)
mem   = 0x52E20 (339488) bytes
cmps  = 0xB3CD1A4 (188535204)
hops  = 0xA08C6AE (168347310)
hps   = 151963.044975
time  =   18.4636 mins  (1107817430400 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 51
seed  = none (default value)
b     = 2 ^ 52 = 0x10000000000000
a     = 2 ^ 51 = 0x08000000000000
P     = 0x0374C33BD548EF02667D61341892134FCF216640BC2201AE61928CD0874F6314A7 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x0EFAE164CB9E3C
s*G   = 0x0374C33BD548EF02667D61341892134FCF216640BC2201AE61928CD0874F6314A7 (33 bytes)
numt  = 0x8 (8)
mem   = 0x80E20 (527904) bytes
cmps  = 0x2428A69D (606643869)
hops  = 0x1FF09B95 (535862165)
hps   = 153719.989373
time  =   58.0994 mins  (3485962802800 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 52
seed  = none (default value)
b     = 2 ^ 53 = 0x20000000000000
a     = 2 ^ 52 = 0x10000000000000
P     = 0x020FAAF5F3AFE58300A335874C80681CF66933E2A7AEB28387C0D28BB048BC6349 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x180788E47E326C
s*G   = 0x020FAAF5F3AFE58300A335874C80681CF66933E2A7AEB28387C0D28BB048BC6349 (33 bytes)
numt  = 0x8 (8)
mem   = 0xDCE20 (904736) bytes
cmps  = 0x1549AA0D (357149197)
hops  = 0x12D22679 (315762297)
hps   = 153038.793388
time  =   34.3880 mins  (2063282714200 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 53
seed  = none (default value)
b     = 2 ^ 54 = 0x40000000000000
a     = 2 ^ 53 = 0x20000000000000
P     = 0x034AF4B81F8C450C2C870CE1DF184AFF1297E5FCD54944D98D81E1A545FFB22596 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x236FB6D5AD1F43
s*G   = 0x034AF4B81F8C450C2C870CE1DF184AFF1297E5FCD54944D98D81E1A545FFB22596 (33 bytes)
numt  = 0x8 (8)
mem   = 0x495C0 (300480) bytes
cmps  = 0xD4FAB0C (223324940)
hops  = 0x115BFA9F (291240607)
hps   = 120565.996454
time  =   40.2602 mins  (2415611495500 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 54
seed  = none (default value)
b     = 2 ^ 55 = 0x80000000000000
a     = 2 ^ 54 = 0x40000000000000
P     = 0x0385A30D8413AF4F8F9E6312400F2D194FE14F02E719B24C3F83BF1FD233A8F963 (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x6ABE1F9B67E114
s*G   = 0x0385A30D8413AF4F8F9E6312400F2D194FE14F02E719B24C3F83BF1FD233A8F963 (33 bytes)
numt  = 0x8 (8)
mem   = 0x49B80 (301952) bytes
cmps  = 0xDFD088B (234686603)
hops  = 0x1208ECAE (302574766)
hps   = 121698.729941
time  =   41.4377 mins  (2486260671300 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 55
seed  = none (default value)
b     = 2 ^ 56 = 0x0100000000000000
a     = 2 ^ 55 = 0x80000000000000
P     = 0x033F2DB2074E3217B3E5EE305301EEEBB1160C4FA1E993EE280112F6348637999A (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x9D18B63AC4FFDF
s*G   = 0x033F2DB2074E3217B3E5EE305301EEEBB1160C4FA1E993EE280112F6348637999A (33 bytes)
numt  = 0x8 (8)
mem   = 0x4A700 (304896) bytes
cmps  = 0x16736A19 (376662553)
hops  = 0x1A8F0CBE (445582526)
hps   = 135532.375726
time  =   54.7941 mins  (3287646391600 nsecs)

ver   = 186, sizeof(unsigned) 4, 128 bit integers, scalar 4x64, field 5x52, 8 processors, 8 available
test  = 56
seed  = none (default value)
b     = 2 ^ 57 = 0x0200000000000000
a     = 2 ^ 56 = 0x0100000000000000
P     = 0x02A521A07E98F78B03FC1E039BC3A51408CD73119B5EB116E583FE57DC8DB07AEA (33 bytes)
k0000 = 0x2DCF462904B478D8
s     = 0x01EB25C90795D61C
s*G   = 0x02A521A07E98F78B03FC1E039BC3A51408CD73119B5EB116E583FE57DC8DB07AEA (33 bytes)
numt  = 0x8 (8)
mem   = 0x4BE00 (310784) bytes
cmps  = 0x34C9808B (885620875)
hops  = 0x39144058 (957628504)
hps   = 153790.653757
time  =    1.7297 hours (6226831609100 nsecs)

Where:

Code:

ver   = the subversion VERsion of the code
test  = the TEST number
seed  = the SEED used for seeding the rand() function
b     = upper bound for the private key search
a     = lower bound for the private key search
P     = the Public key
kXXXX = the tame Kangaroo IDs used (needed if more than one tame kangaroo is required)
s     = the Secret (private) key found
s*G   = calculate the public key to double check the results
numt  = the NUMber of Threads
mem   = total amount of dynamically allocated MEMory
cmps  = total number of point CoMParisonS
hops  = total number of HOPS
hps   = Hops Per Second 
time  = TIME it took to find the private key

People who have volunteered to help with testing (listed in alphabetical order):

Quote

agatazit
AirShark
AndreuSmetanin
Angelo1710
arulbero
asher1101
ayiphelmy
bulleteyedk
byyuans
Darmont33
dextronomous
Firebox
iparktur
JDScreesh
johan11
miningforprofit
PietCoin97
sanhwy
stivensons
supika
Telariust
ultramen
vimp666
ZafotheNinja
zielar

Topic: Science Fair Project to trap Bitcoin private keys using Kangaroos! (Read 7850 times)