Pollard's kangaroo ECDLP solver - page 122.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: Etar on May 27, 2020, 08:08:01 AM

@JeanLuc in next release if it possible fix please addiding date string to workfile before extention.
I mean i use file -w savework1.part but after saving got savework1.part_27May20_160341 should be savework1_27May20_160341.part I think. Thanks.

Edit:With -d 28, -wi 600, memory usage by server 10-20MB( it think -wsplit is great tools)

I recompiled a version that does similar to what you asked.

Simply changed the code in Backup.cpp

Code:

string fileName = workFile;
if(splitWorkfile)
//fileName = workFile + "_" + Timer::getTS();
fileName = Timer::getTS() + "_" + workFile;

works as described.

Instead of saving as savework1.part_27May20_160341, it saves as 27May20_160341_savework1.part

This way your .part extension is at the end of the file.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

With the new -wsplit option:

How are you using it?

The way I read, it saves an updated file let's say every -wi 60 seconds. Got it. I've tested it.

So the only way the key can be solved on the server side, is if a collision happens in the current, being worked on, reset/smaller hash table (the one that will be saved next)?

The server doesn't compare the different saved files for a collision, so one must merge the different saved working files to check for a collision.
If you have 10, 20, 30, 100, 1000 saved files over a period of days, weeks, months, are you manually merging the saved work files every so often?
The current merge option only allows the merge of 2 files at a time...manually merging could become an hourly task (depending on how many files you have being saved each minutes/hours.)

So you have a benefit in RAM but increases the amount of work you have to do in merging files?

Etar

sr. member

Activity: 642

Merit: 316

Quote from: zielar on May 27, 2020, 03:14:19 PM

You fell from heaven with this tool, man! Just tell me how to set -ext knowing that the latest release adds the ending without .part?

-ext you can set what ever you want, just it was a word in the name of small files.
Example. you have -w mysmallfile on server, when it will be save with -wsplit it will look like mysmallfile_27May20_232415
So you need set -ext like smallfile or small.. if only the grabbber could distinguish this file from others

patatasfritas

newbie

Activity: 17

Merit: 0

Quote from: MrFreeDragon on May 26, 2020, 01:50:48 PM

Jean_Luc, I want to look at the table which is saved to workfile. But as I understood, only 128bit are saved for X-coordinate and 126bit for distance (together with 1 bit for sign and 1 bit for kangaroo type).

Anyway, what is the easiest way to receive the whole table in txt format. I easily could read from binary file the head, dp, start/stop ranges, x/y coordinates for key. After that the hash table is saved with a lot of 0 bytes....
Can you just briefly describe the hash table structure which is saved to binary file?

if you still haven't managed to export the workfile, here are the changes I made to the code to export the DPs to txt.

The X-coord is 128+18 bits and distance 126bits. The X-coordinate could be re-generated from the distance if necessary.

https://github.com/PatatasFritas/FriedKangaroo/commit/1669df5f91ef2cc8a7619b21f66883fa164ab602

zielar

full member

Activity: 282

Merit: 114

Quote from: Etar on May 27, 2020, 02:38:25 PM

If someone wants to run a solver with small DPs, but the server’s resources don’t allow it, then you can use the -wsplit option,
which appears in version 1.7 of the solver.
But in any case, you must have a PC that can merge files. I just had such a problem.
Now I can safely merge files on my home PC. In order not to do it all manually, you need a grabber and a merger.
File grabber is launched on the server, merger is launched on the home PC.
Merger communicates with the grabber and requests files from him. The graber sends, if any, and then removes them from the server.
The merger, in turn, after receiving the file from the grabber, starts the merge process, during which it is possible to find the key, after merge temp file deleted.
Grabber gives files only to an authorized merger.
If it helps someone, archive with source codes, compiled programs and example .bat files: https://drive.google.com/file/d/1YB3tz_tkJWTilXMCm_3GIfKsODGzDTqi
As before, the sources under Purebasic.
mergeServer(grabber):

Code:

-pass >password for merger authorization
-port >listening port, where merger will be connect
-ext >by this extension, the grabber will search for files in the folder,
for ex. using -ext part, than you should start server with -w xxxx.part

mergeClient(merger):

Code:

-jobtime 60000>request a file from the grabber every 60s
-name >it is name of your merger, useless, just for stats
-pass >password for authorization(should be the same as in grabber)
-server >host:port grabber
-workfile >name of your masterfile
-merger >Kangaroo.exe by default

You fell from heaven with this tool, man! Just tell me how to set -ext knowing that the latest release adds the ending without .part?

Etar

sr. member

Activity: 642

Merit: 316

If someone wants to run a solver with small DPs, but the server’s resources don’t allow it, then you can use the -wsplit option,
which appears in version 1.7 of the solver.
But in any case, you must have a PC that can merge files. I just had such a problem.
Now I can safely merge files on my home PC. In order not to do it all manually, you need a grabber and a merger.
File grabber is launched on the server, merger is launched on the home PC.
Merger communicates with the grabber and requests files from him. The graber sends, if any, and then removes them from the server.
The merger, in turn, after receiving the file from the grabber, starts the merge process, during which it is possible to find the key, after merge temp file deleted.
Grabber gives files only to an authorized merger.
If it helps someone, archive with source codes, compiled programs and example .bat files: https://drive.google.com/file/d/1wQWLCRsYY2s4DH2OZHmyTMMxIPn8kdsz
Edit: fixed little memory leak at grabber side.

As before, the sources under Purebasic.
mergeServer(grabber):

Code:

-pass >password for merger authorization
-port >listening port, where merger will be connect
-ext >by this extension, the grabber will search for files in the folder,
for ex. using -ext part, than you should start server with -w xxxx.part

mergeClient(merger):

Code:

-jobtime 60000>request a file from the grabber every 60s
-name >it is name of your merger, useless, just for stats
-pass >password for authorization(should be the same as in grabber)
-server >host:port grabber
-workfile >name of your masterfile
-merger >Kangaroo.exe by default

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: Etar on May 27, 2020, 11:17:06 AM

I tested -wsplit in the 89bit range. Works perfet! Thanks JeanLuc.
Grabber take files from server and send to local PC, where merger merged this files with masterfile.
Key solved during merge after 32minutes on 2080ti. I did not wait until the key is solved on the server, enough that it was found through merge.

Many thanks for the test

I'm currently working on the merger trying to speed it up and decrease memory consumption.

Etar

sr. member

Activity: 642

Merit: 316

I tested -wsplit in the 89bit range. Works perfet! Thanks JeanLuc.
Grabber take files from server and send to local PC, where merger merged this files with masterfile.
Key solved during merge after 32minutes on 2080ti. I did not wait until the key is solved on the server, enough that it was found through merge.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: arulbero on May 27, 2020, 10:29:59 AM

-snip-
Different private keys, different positions, different points, different public keys.

Ok, got it. It is the group axiom.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: MrFreeDragon on May 27, 2020, 10:14:14 AM

Quote from: arulbero on May 27, 2020, 09:50:46 AM

-snip-
1) for each private key there is only 1 point (n private keys, n points, n is the order of the curve)
-snip-

I know that EC collision is not proved as there is no example.
Yes, for each private key there is only 1 point, however not necessary that if we have n private key we will have n different points.

Simple example for the group of 10 elements:

Code:

Key Point
1 7
2 6
3 5
4 7
5 3
6 2
7 7
8 0
9 9
0 7

You can see that for each key (0..9) there is only one Point, i.e. we do not receive 2 or 3 or more points for each key. We have only one point. However key 1,4,7 and 0 lead to Point 7 (collision). For group of 10 elements it is easy to check.

However how could you be sure that for group with almost 2^256 elements for every private key we have the unique Point?

'Group' has a specific meaning in math, it is not a simple set of elements, moreover a group with a prime number of elements has the property to be cyclic, i. e. you can 'generate' each element using only one element of the group (but not zero) and using the operation of the group: adding it to itself: G, G+G=2*G, G+G+G=3*G, ..... it is like to assign a number, a scalar, a order to each element from the point of view of G.

In the secp256k1 the group is a group of points, a cyclic group, and each private key is the 'position' of each point from the point of view of G (a chosen point). Because it is cyclic, when you perform G, G+G=2*G, G+G+G=3*G, ...., you generate all the elements of the group before to return to G.

Different private keys, different positions, different points, different public keys.

If you apply the Fermat's little theorem in a additive group, a*(n+1) = a, a+a+a+a+a....+a=a and
(n+1)*G = G.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: arulbero on May 27, 2020, 09:50:46 AM

-snip-
1) for each private key there is only 1 point (n private keys, n points, n is the order of the curve)
-snip-

I know that EC collision is not proved as there is no example.
Yes, for each private key there is only 1 point, however not necessary that if we have n private key we will have n different points.

Simple example for the group of 10 elements:

Code:

Key Point
1 7
2 6
3 5
4 7
5 3
6 2
7 7
8 0
9 9
0 7

You can see that for each key (0..9) there is only one Point, i.e. we do not receive 2 or 3 or more points for each key. We have only one point. However key 1,4,7 and 0 lead to Point 7 (collision). For group of 10 elements it is easy to check.

However how could you be sure that for group with almost 2^256 elements for every private key we have the unique Point?

BitCrack

jr. member

Activity: 30

Merit: 122

Quote from: arulbero on May 27, 2020, 09:50:46 AM

Quote from: MrFreeDragon on May 27, 2020, 09:23:59 AM

Quote from: arulbero on May 27, 2020, 07:40:30 AM

-snip-
There are about 2^256 points, then 2^255 different X-coordinates (k*G and -k*G have the same x-coordinate).
-snip-

Is this proved fact?

I mean why every private key leads to the unique X-coordinate? (except for symmetry point).
In other words, if k and (order-k) leads to x-coordinate Xk, how could we be sure that there are no other key m leads to Xk as well? (m differs from k and (order-k) )

Because it is proved that:

1) for each private key there is only 1 point (n private keys, n points, n is the order of the curve)

2) for each x-coordinate, the y-coordinate must fulfil this relation: y^2 = x^3 + 7 mod n;

each equation of the form y^2 = a has or 2 opposite solutions (+y and -y -> k*G / -k*G), or has no solution.

Therefor there can't be 3 different points with the same x-coordinate and with 3 different y-coordinate, because there are no 3 different y solutions for the equation y^2 = a mod n.

We know that there are exactly (n-1)/2 different x-coordinates (and (n-1)/3 different y-coordinates)

That's how the math works. The points on the curve form a group (https://en.wikipedia.org/wiki/Group_%28mathematics%29) and the point G is a generator of that group.

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: MrFreeDragon on May 27, 2020, 09:23:59 AM

Quote from: arulbero on May 27, 2020, 07:40:30 AM

-snip-
There are about 2^256 points, then 2^255 different X-coordinates (k*G and -k*G have the same x-coordinate).
-snip-

Is this proved fact?

I mean why every private key leads to the unique X-coordinate? (except for symmetry point).
In other words, if k and (order-k) leads to x-coordinate Xk, how could we be sure that there are no other key m leads to Xk as well? (m differs from k and (order-k) )

Because it is proved that:

1) for each private key there is only 1 point (n private keys, n points, n is the order of the curve)

2) for each x-coordinate, the y-coordinate must fulfil this relation: y^2 = x^3 + 7 mod p;

each equation of the form y^2 = a mod p has or 2*** opposite solutions (+y and -y -> k*G / -k*G), or has no solution.

Therefor there can't be 3 different points with the same x-coordinate and with 3 different y-coordinates, because there are no 3 different y solutions for the equation y^2 = a mod p.

We know that there are exactly (n-1)/2 different x-coordinates (and (n-1)/3 different y-coordinates)

***EDIT:

according to the Fermat's "little theorem"

https://brilliant.org/wiki/fermats-little-theorem/

a^p = a, then a^(p+1) = a^2 mod p then a^(p+1)/4 = sqrt(a) mod p

(note: in the secp256k1 p = 3 mod 4 then p+1 = 4 mod 4)

if y = a^(p+1)/4 is the sqrt(a) then y = -(a^(p+1)/4) is the sqrt(a) too, i.e. to the power of 2 they both produce the same result, a, that in our case is X^3 + 7.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: arulbero on May 27, 2020, 07:40:30 AM

-snip-
There are about 2^256 points, then 2^255 different X-coordinates (k*G and -k*G have the same x-coordinate).
-snip-

Is this proved fact?

I mean why every private key leads to the unique X-coordinate? (except for symmetry point).
In other words, if k and (order-k) leads to x-coordinate Xk, how could we be sure that there are no other key m leads to Xk as well? (m differs from k and (order-k) )

Etar

sr. member

Activity: 642

Merit: 316

@JeanLuc in next release if it possible fix please addiding date string to workfile before extention.
I mean i use file -w savework1.part but after saving got savework1.part_27May20_160341 should be savework1_27May20_160341.part I think. Thanks.

Edit:With -d 28, -wi 600, memory usage by server 10-20MB( it think -wsplit is great tools)

arulbero

legendary

Activity: 1932

Merit: 2077

Quote from: MrFreeDragon on May 27, 2020, 07:24:41 AM

Does anybody know how to estimate/calculate the total possible DPs within the range? Moreover, it is also possible that for some DP value there will not be any DPs.

For example, the minimum X-coordinate value I know is for private key 7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 and for 7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1
Their X-coordinate has 90 leading zeros, so it is DP=90

Probably there are only 2 X-coordinates with 90 leading zeros, and no more.

There are about 2^256 points, then 2^255 different X-coordinates (k*G and -k*G have the same x-coordinate).

Probably there are:

2^255 / 2 X-coordinates with 1 zero leading bit
2^255 / 4 X-coordinates with 2 zeros leading bits
….
2^255 / 2^90 X-coordinates with 90 zeros leading bits
…

If you sum 2^254 + 2^253 + ….+ 2^165 + …. = 2^254 (1/2 + 1/4 + 1/8 + ...) = 2^254 X-coordinates with at least 1 zero leading bit.

With DP very very large (like DP=250) you can manually determine how many x-coordinates there are (if there are) such that Y^2 = X^3 + 7 mod p

On average 1 number each 2 is a valid X-coordinate (for a estimate).

Here there are 150 X-coordinates with (at least) 40 zeros leading bits:

Format:
X-coordinate private key
* stays for: private key * lambda
** stays for: private key * lambda * lambda

Code:

0000000000e1387e34763704d1b149a7cdc086395346907a49ed7963ae5e4837 3400000000000000000000000000000000000000000000000000000035d80cda *
00000000000782001b949535174e508842e6945495da73f59adb47064176d233 010000000000000000000000000000000000000000000000000000007a44c2f0
000000000078584f51938406db35438ed5c4189f2fd2b1e6ca8a6a2179bbd808 400000000000000000000000000000000000000000000000000000007121b07e **
0000000000eaf2052284bdad2bf8cd17d99b2ffe046244a0044b261f8df674a8 4300000000000000000000000000000000000000000000000000000127924a01 **
0000000000746daafebc7e7d83963f657a9546fff669bbab8ec785946a7059ca 4e0000000000000000000000000000000000000000000000000000039345bfcd **
00000000000e258648b5edddf578a965f74363983fee1fa2fc9af00720c3c79d 2000000000000000000000000000000000000000000000000000000564b8a5ec **
000000000038641aed1bb3ea0b9eba5f75da61de20da2f9b5c2ba9e7f8ce47e5 04000000000000000000000000000000000000000000000000000006c2049732
00000000003161df5d55df74ea73f01281bd8da8926bd9fab14e69c0162f9821 4d000000000000000000000000000000000000000000000000000008bf8f3af4 **
00000000000ba89625cdfc9561b2ba99b8726d904115cbeae6823bde71aa52b0 03000000000000000000000000000000000000000000000000000009339b1d3a
000000000048d030ecd0e435656bb8645cc65914af61b30834b4793062e9c306 07000000000000000000000000000000000000000000000000000009b9cd0716 **
000000000037527338a68f66379f010f6e001ec69175d8dde8606687068b64b6 2e00000000000000000000000000000000000000000000000000000a88164703 **
0000000000114ab80b0e1804be9a7720ebd23000298d45f1e126c4329026b387 3600000000000000000000000000000000000000000000000000000bc53beb3d
0000000000ca3291e849f0b2923ab4217c419a1a665c7aba06a5c422df7387a2 2f00000000000000000000000000000000000000000000000000000d9dafab78
00000000006abf9e3898b80935072e5e54f75d78139698321a079765fbb87077 4400000000000000000000000000000000000000000000000000000f7cc1c6e0 *
000000000082d7e503357813e06a1d496304099dd11156d6059837880a8a3852 400000000000000000000000000000000000000000000000000000112b4092c2 *
0000000000be7f258426d9fa89cbc7c04ffbdef4279bd9b797dc41951cec9ea8 47000000000000000000000000000000000000000000000000000013433071df *
0000000000be1e4abfe878e51be079b3da54f95ef87043ef131a38555d90b288 210000000000000000000000000000000000000000000000000000144097c2c6 **
000000000062eb05bda779f9d06aabd0710c96f9b9835e92af344df20e16b280 4a000000000000000000000000000000000000000000000000000014892c0ecc *
0000000000e14b6206085b683ca9cb4d18ba897fc140b72d5d4a98e85e848393 2e000000000000000000000000000000000000000000000000000012e841e014
000000000099d3ee7e7e15306ec2ed021fee5a4bf7446e3ed801a6b9ad43bc7e 3200000000000000000000000000000000000000000000000000001586220c38
0000000000290459244c0db66eb013fd5ed2fbc4b065e93c4bbe7789431840ef 4900000000000000000000000000000000000000000000000000001795d5ee70 **
00000000009370afb5c0787686cf10b47aa16de5b57bfcee6085c863cbdde7be 0f00000000000000000000000000000000000000000000000000001c4b397168 **
00000000002970866989ac7adc6e39f092b750b157d1fd0ff88b7cab6c15069d 2c00000000000000000000000000000000000000000000000000001aee157f73 **
000000000056a12f7211ec469bda752225200948a9df628ec29fdd71d7b1f255 4e00000000000000000000000000000000000000000000000000001b25cfb7fa
0000000000ffe1af9405c6cb2cd0301d205e438c3acfcb89f6706c0991747dff 4700000000000000000000000000000000000000000000000000001eb6d634ed
00000000005b407be3fd7fce7e511f36b98c0d6c6d2b41e36be06b1fa55b9d18 010000000000000000000000000000000000000000000000000000206053b7e1 **
00000000004d0c8af1e64a02cbe2515dbed58305db33d0fe607ff8d65e59fb4d 2600000000000000000000000000000000000000000000000000002059016305
0000000000d607ab339cd53605e3daed98ab12b56454a9c390be43b776e2bbd8 4700000000000000000000000000000000000000000000000000002192d3ae07 **
0000000000ba690b40254396533f88548f47e370aba84161d0a6acd3ae7d98d5 0f000000000000000000000000000000000000000000000000000022802481ec *
00000000005e014bd8b52e557973bad624de8338f64fdb4966c90c2c6c30f072 4400000000000000000000000000000000000000000000000000002305df5f3b *
00000000006dd652e5f2dbf67105fa9f4848a2802650923b8dd8fec131d2c1e5 2100000000000000000000000000000000000000000000000000002483eca1c2
0000000000eee298ef6f932424a042c527b319df421d913be6e724f6844f791f 08000000000000000000000000000000000000000000000000000023d5710442 *
000000000098db3e2daff3bddb91f1b25fecd1e3c1d7688969435002b8743874 420000000000000000000000000000000000000000000000000000259b17ecd4
000000000038a17c2c2b48aae4c3c42fcbd95c921f266173f092d6238f7467ea 2500000000000000000000000000000000000000000000000000002b10295811
0000000000f78db9d6dac133bf88b3fce552a3a7b5798c83d215035e07e4030e 21000000000000000000000000000000000000000000000000000030f69dc72f **
0000000000483f6501b75d009dbe425aa3851458c9f0c8ea577d4e1132e0f36b 2b00000000000000000000000000000000000000000000000000002da0cd8973 *
0000000000833c64a5fd1427db5b4bce13e3a458a3d292ef8be0ac990a043fb0 29000000000000000000000000000000000000000000000000000031b4ea599b
0000000000bac1d94f9a5e69f561a7d8ac473982853e86d5799347a6b7040eec 3b000000000000000000000000000000000000000000000000000031dc250688 **
0000000000b11f8f7eb05d351666635b17fa37a6374ea9a1d67b9b9f29f47de7 06000000000000000000000000000000000000000000000000000035fb9e34d5
000000000028c1271f0622c76e509a557a22e52984b1dbd43a8ff3b41a6be038 3300000000000000000000000000000000000000000000000000003cb2fd81f6 **
0000000000c3b83a49bff16735966b68db9fb807ee16bc578493e649a71b7ea2 3000000000000000000000000000000000000000000000000000003dda8a0178 *
00000000005aad53d073eb42cd5561c51c25556890430f8211fb5972582cc2af 0f00000000000000000000000000000000000000000000000000003e073c0aa4
0000000000fef7b9f0625f3b0276e7117297014b5a6b6737a6b734c6b32299e8 43000000000000000000000000000000000000000000000000000045b8c64bce
0000000000ba5e3cf798dca0106b04cbff25454bcb17b7ffbad40835ee80416b 3d0000000000000000000000000000000000000000000000000000417926772b **
000000000030a634abf8c070efe2849bf43215a03fda87bc8e599f6a44c041f5 4300000000000000000000000000000000000000000000000000004e6c029d43
00000000004fc29e693ec13174cd39d04df405a9fcca7aa751a3064b16393d9d 2600000000000000000000000000000000000000000000000000004e9e2d59af *
00000000008eeb95a7921daf9a41c44e42c55e5982af59cb144180869aa33907 4e00000000000000000000000000000000000000000000000000004a46aa2b34 *
0000000000e12a2ca86763caacd41da5543495ef3a9881bc181dbd19a1789eb3 0400000000000000000000000000000000000000000000000000004b27f4845d *
000000000034fa8aaff56d58e627686500ce964c65bf2075de1f2e0a16a8d27e 0600000000000000000000000000000000000000000000000000004c6e1a1072 **
0000000000fe2c73cc34c728e4b708ec9285ae522d951e9e37456dde6e2362af 4900000000000000000000000000000000000000000000000000005507b31e91 **
00000000008a87569d8d490adbe8be0374801b08025689a0015a9fa8b00baa55 22000000000000000000000000000000000000000000000000000056cad544ce
0000000000f1915530ace1a1ef5e20e998454d508a7fa76817a09d42180adeb2 0500000000000000000000000000000000000000000000000000004eea8f5b2e **
0000000000d8638ee149f9bb8da1ce3c02c3c8db4ed04e7600bac3685f999f55 3c00000000000000000000000000000000000000000000000000004f22521c79 *
0000000000b5ca55257a99cc520c9035214d0e34fb458f40b86f42462c710625 2c00000000000000000000000000000000000000000000000000004fd2b2ac94 *
00000000001f535fb63eb670c4dc5d0dd40874be572442b7910e6b7ea4a3689b 03000000000000000000000000000000000000000000000000000058393eef1c
0000000000b6d78d481bf5ad67894636c5cad6f33af463b3e9b652101839deaa 2f000000000000000000000000000000000000000000000000000059187ad834 *
00000000005a6d135314ded19d69f458661c81a90e35af1b585b10cf81e7b1bf 0f00000000000000000000000000000000000000000000000000005e4fb22f07
0000000000542367426192dcce71b8a7ac92e477a29e99fc840317a211f79c60 0400000000000000000000000000000000000000000000000000005735a34760 *
00000000000d1c9cc3554547e4542e6d30a8eeaf2dc7e2182deff4a76c3c198b 49000000000000000000000000000000000000000000000000000061206d1637
0000000000691a54d41a653a459b55e0f0737615bfc27590ec33621b0fb1f734 2c0000000000000000000000000000000000000000000000000000581d4e7d1b
0000000000b67570c5e65ae0d835b7bcf50ca47c6a21a8a2a3e50b7e60acf6af 01000000000000000000000000000000000000000000000000000062daabe2b9 *
00000000008f8ef820dc55048ec0715215d80326bd6f1f8d71efcd572ab29a42 2b00000000000000000000000000000000000000000000000000005a7ffa68e5
0000000000411539289a4781aaf72a0456c936f009d1c0ab3d7f5b4317f4764e 2900000000000000000000000000000000000000000000000000005b2a787e2f *
00000000009d7b09b73cd3812d36308f0bf7804b75839c2729258057d0c8b9ec 0b00000000000000000000000000000000000000000000000000005c0a5334f0 **
0000000000aabb9b35a915f6c77bfd5170d985183e278182010a80b5b2683c4e 2300000000000000000000000000000000000000000000000000005f0563a0ed **
0000000000e5e766bec583623deb624ea842dd2a6f60efe181b7af3e5b7dfeb0 440000000000000000000000000000000000000000000000000000697801457e **
0000000000f58fb64342b9533078d1ec060a6a29c5a4cdf22c857a5b02cee950 0300000000000000000000000000000000000000000000000000006b64cb9050
0000000000d25e501ff4f3a4b5c4f0347890ab5fcda1b611c52556e191112030 4300000000000000000000000000000000000000000000000000006b7f6a8329 *
0000000000f875c007ba88691c8477b9dd01314787e35bd92e7a7c5a3442dd5b 2e000000000000000000000000000000000000000000000000000061c490d4cb
000000000038404839b0f3494e427561da52a2e10aec1ac1f541944014cece67 2500000000000000000000000000000000000000000000000000006c6ad7b2c6 **
0000000000c6e3b1cb698550687f04bb2f82b700051a0253e764354d623cd36a 45000000000000000000000000000000000000000000000000000065cd18e99e *
0000000000a1a98496830705c31c82068ffbe91f7a770fda95089aa0cc3f6131 44000000000000000000000000000000000000000000000000000070f6dcf30c **
0000000000731c7a6cd5b6a333fbe3912494a80027ce723786e344e9c2eb6cf3 4f00000000000000000000000000000000000000000000000000006746697a3a **
00000000000253580efde16e545eab16a2d7be688efc24a500b18e2bbce156f2 500000000000000000000000000000000000000000000000000000765c403c76 *
0000000000da58d85ba8a98e602c02123733ce84f561a5d5f8177e2d495179b5 4d00000000000000000000000000000000000000000000000000007803ee1e7d
000000000048385ae72fae801c416042100363d8611c02f84db58a446102c549 2100000000000000000000000000000000000000000000000000007a7fab6f0f **
0000000000c4a454b75451b80fb0daf9efb2f730016a569c0135671c3a8ea662 4400000000000000000000000000000000000000000000000000007c5512329a *
00000000009be1da57e2754f165ae552f7650c289c2e1b10340b88479f5e074d 2b0000000000000000000000000000000000000000000000000000715e7a06c7
000000000029c788db8614f2c9f8c70b8c81d8b53ab875f94fbc858a74e2aff3 4700000000000000000000000000000000000000000000000000007d501ddb96
00000000008076195f44f6b2530a26a812dec1c55aad4ed89d5cad8f4cd66cb5 04000000000000000000000000000000000000000000000000000072b66b2c33 *
00000000002324fbf67e2c9b409555d5f81a1a9cf357ff13d5dc6fb511b7b3c5 2d000000000000000000000000000000000000000000000000000072eed6e554
00000000007a5e928750d176684dcb02202551424bd57d13f3b2a4a4a4956c1d 2100000000000000000000000000000000000000000000000000007f913a342b *
000000000090acd365c1c11dc24bea76fa08e6491b7a55e09f10282d0ada4718 310000000000000000000000000000000000000000000000000000820bc69995 *
000000000031fa63e3a177772f6f76e89df5a56950d06b51299be11e78293762 0d000000000000000000000000000000000000000000000000000081b0853f24 **
00000000002d30483dca9336707222d46108bec30e1554a6637199cdf6b50596 0d0000000000000000000000000000000000000000000000000000830449eaa2 *
00000000007ccea2cf2527c0baf148ce9b60798ed51e048a2475b70b7d714ab5 33000000000000000000000000000000000000000000000000000086ba56b214 *
000000000017d8ca47fdf6d84ffdf1c23cce89cafb23d6147e47e5a696529311 4a000000000000000000000000000000000000000000000000000087a063a3a1
0000000000ddbadde727101e7492adf72efb023ffc994350c713a69802985345 4f00000000000000000000000000000000000000000000000000007c12c9d6b3 **
0000000000e2613d7a3dd37d3ab1a815292bc223be8e687f6d8f01f754893214 2f00000000000000000000000000000000000000000000000000008bf4560dae
00000000005359833eb0fea79476bd0da7780923d73f461f0055fc741056a4b4 0f00000000000000000000000000000000000000000000000000008ec44724c9 **
0000000000d4eba0b7121349d12296f6ddd395b8914e4edb6c1f8b2dda2c0798 4b00000000000000000000000000000000000000000000000000008fa05aa0e7
000000000030b6fc85b2d25ee0be4c846a92b1fa6ff756b08a5e31bcf7f06dec 0e00000000000000000000000000000000000000000000000000008fe8f66ffb
00000000002a2e84da8c225da3a9d2a8a834a2f19c65abb3b9e434de6940e16f 34000000000000000000000000000000000000000000000000000090397cebd5
00000000004c52b3b730eba8a698da108eb4441c4714e8e32a1454e51d8ba993 220000000000000000000000000000000000000000000000000000911b844bf7 **
0000000000e59f8a0a1a4fd30bd6de4e763f91b54068fc82b703750a73a020e8 4400000000000000000000000000000000000000000000000000009235f29813 **
0000000000cf5cc10c465fca5265d33220517fde05263e6bbd552662ee61b63b 43000000000000000000000000000000000000000000000000000093ebe05e84
00000000000207fd60bf7dbca3668484c5d053f44d2c8aadd153083bffdd3f89 33000000000000000000000000000000000000000000000000000094d0503fd8 *
00000000007a985a0552010b70f94f92c277dc829c906ee227140e2adc4fc23d 4700000000000000000000000000000000000000000000000000009642517f25 **
000000000066c692da677bb343380010bcc124979b105c3aefa8d61ae396d7ec 3c000000000000000000000000000000000000000000000000000088f556a035
0000000000e7ac2331180800284e5845ddcf86269ad11703575c040034da66d2 0300000000000000000000000000000000000000000000000000009772222066 **
0000000000112e611dfef0b3337d76c72678d9bdd278746576f433737c1119ed 2000000000000000000000000000000000000000000000000000009a8c9a00d5 **
00000000006c8b085094fb4e24e6de5ec3077645474429b8a86945806172600f 5000000000000000000000000000000000000000000000000000009bd0b9b743
0000000000039135669de01b5b71c7b1b4c95f73bc7cc51e31edee7652684693 2800000000000000000000000000000000000000000000000000008f618b083a *
000000000039408d8b1e157086cb54541e67379245b04b79825ba9ce9d78fc84 0d00000000000000000000000000000000000000000000000000009d0a17aff4 *
00000000006f7c43be15a16cd70799c9b5d8dc65d0ccc1ee4459dcee5af8d306 4d00000000000000000000000000000000000000000000000000009ec63479c0 *
00000000000f6d6e4830d80db23e334ca39d2e04147def72c708357e438888ed 3400000000000000000000000000000000000000000000000000009ed94586d5 *
0000000000c98b36474cb55e62061cfb08bfd4ce3a69b5ca9c7f08588b6f76f6 330000000000000000000000000000000000000000000000000000a3aac478a3 *
0000000000627289388cc776ce9a756172becec7f003d2add6d04349523da871 4a0000000000000000000000000000000000000000000000000000a407ab0e21 *
0000000000adaa5aba99cee89ab3dea36df0ff857569a364606a74e5531c2dde 3b000000000000000000000000000000000000000000000000000096074b6fea
0000000000588f27926ae621e31abf67ab42441a1e700a09cc920fd741ae0f4a 220000000000000000000000000000000000000000000000000000a5f2db612f **
0000000000dc1056e8966e266feee9bd7fa7f12195d6a5827744130caf2be165 4a0000000000000000000000000000000000000000000000000000a6e5e544c6 **
0000000000169624fd93b346d9ac1a8a96153d4e148ad5f9018bcb698ac32cb4 4e000000000000000000000000000000000000000000000000000098d3fe967f **
000000000026579cd3cafe37b1377dbee59285b2d422e0fe6219534f08175318 270000000000000000000000000000000000000000000000000000a971ef2767 *
0000000000bfab61136dd4460e11a1ffa3b17fa9421485dccb6930a433fabdd0 2a00000000000000000000000000000000000000000000000000009b5af6e011
000000000075372605aa10b8771bddd17464539100ba9f47c32bf6ac3099d840 260000000000000000000000000000000000000000000000000000ac14a68606
0000000000ac364c92cbe22a8ff92fc0642e01cc659001194310bfcfc66e38bd 440000000000000000000000000000000000000000000000000000acfdbfd97d
00000000005fae112ce4da7dbfa36aea6324b4d815e077c53c2dfde10d050218 2f0000000000000000000000000000000000000000000000000000ad6b56e5f7 **
00000000008321a1d2320c4ecebd698d2108947a18e730f27834d75d4d019bb9 030000000000000000000000000000000000000000000000000000aef9b3cbf4
0000000000c7e9a68c1311d1f5b1e951da610cdb7f80e8cdf155777e8e9ceacf 0a00000000000000000000000000000000000000000000000000009f05e15040 *
00000000006317687ee6b576aedc218ac50292c45fac9820343d1ae8a1822ffe 0c00000000000000000000000000000000000000000000000000009fb91aaa95 *
0000000000452c2cc77cf66afb4f42740e8f630d0b1e2981e61eb8296a0e7ac8 260000000000000000000000000000000000000000000000000000b073179dfc **
00000000002dd16b14908b8c1ba6da36ecc3b2e9469056cf5ea42b7987e79136 490000000000000000000000000000000000000000000000000000b0c0e4466b
0000000000fa05621b01c9f30bba03606d46baee37dd437ba10fab8bf526bebc 2b0000000000000000000000000000000000000000000000000000a0c7c3b794 *
0000000000223426109e52acaa063c438e5ccce76922c6f4b9352633e1a6bb77 410000000000000000000000000000000000000000000000000000b1dc215d63
000000000021bcb0a92153e443c18afa3fcc73e8c8bf9f26b54f77b24177116f 270000000000000000000000000000000000000000000000000000b348affb47
0000000000337663bacac49e6ed1a431432c4c662b4047eab600a4a4e3332bed 3d0000000000000000000000000000000000000000000000000000a36c50588d *
00000000001b397027145fb70ae3bb9d2849716d050806112f026c30a044278c 3b0000000000000000000000000000000000000000000000000000a5334cdcbf *
0000000000d628316a177fd9a79704dc823548a4fc4e7e84b60a30a9a35c8a4d 020000000000000000000000000000000000000000000000000000b714c45726 **
000000000031f3e0bad056f386d03e5d7886c32a2a47df7e8f3217e9fc83e6f2 4c0000000000000000000000000000000000000000000000000000a878a87de5
000000000098362b7600b230158a1d525dc5a8fee96ccbbf92ba2d074d0db510 390000000000000000000000000000000000000000000000000000a9fe4d0a17 **
0000000000d8ccf602e3af80b9954861c7e45c9c89b499ee4af5bef1be80db64 430000000000000000000000000000000000000000000000000000bb61a856f3
0000000000fee30227eabdcdb52b95c29d5cc65b23fffd0c3c938462211e9fc4 0c0000000000000000000000000000000000000000000000000000aa95799d6d **
00000000005500e528180e0f73791b72902c86f738a94d926b3c1d4141c29df2 2d0000000000000000000000000000000000000000000000000000aaf227f829 *
0000000000c4eb35f18e40c5165a79e774acc7aca1cbee807f8e8261867b4b4c 270000000000000000000000000000000000000000000000000000be0795d1e7 *
000000000056a879256aec5d8d6b93d31c136b087435dc42a3751e6690bfb2fa 010000000000000000000000000000000000000000000000000000bed691b491 *
000000000072f5b4177f22f5e626fd63deeaf017966508e0b636fc7fc41d431e 2b0000000000000000000000000000000000000000000000000000aec4c14f3a
00000000009536e5f4bd9d45e0b3b3a83026926d949306b900611ee66dc31ea9 230000000000000000000000000000000000000000000000000000b083ac428d *
0000000000a94bcd761a48e8680e4813851534ea107c9f98903932f1e42a6c51 4f0000000000000000000000000000000000000000000000000000af22924a9b
00000000001abeda8db6a1dbe86b406e5c8fccada7f8def3ead2e3c94e7cf96c 050000000000000000000000000000000000000000000000000000b011bc6424
0000000000c08c7bc3d0652958b0e3b97f11ffa45c721a0c950d38931df477b9 3b0000000000000000000000000000000000000000000000000000b0e3acd01c *
000000000074d7fb5967621d123ff71a5b4ad68e88c73631d4c2dfa31426a328 4f0000000000000000000000000000000000000000000000000000b5ac2f001f **
00000000006ca7c7b5621997a3b6ce0a3d66fc7628c522568fb6573504a849f9 4f0000000000000000000000000000000000000000000000000000b7045a8bca *
0000000000610b670ee3b913a18601789ce3a57c0426bc2d70c5cac09889ff1f 060000000000000000000000000000000000000000000000000000b7bb58a8cb *
0000000000f8bae0431e5c5b0283b27b1356e2207c9120c1b2bbfaf9dfaf070f 3b0000000000000000000000000000000000000000000000000000b7ff5a755c **
0000000000235e55ec3eefdebcf11a413ef9be888ff1ba88c24e59da6feca9d0 280000000000000000000000000000000000000000000000000000ba37b4884f
00000000009dfca60babadf0feb0947dd82d7f46a7f0509760663e77130282c9 4f0000000000000000000000000000000000000000000000000000ba1c0b4195 *
0000000000b0c422feb134aedf781fa05c5fafa4c2babef090ef6f7a3291d7f6 2d0000000000000000000000000000000000000000000000000000bad45c7245
00000000007c0a55e740d6580d28ab871218bd9c01199cbe837b24fd16e7c3ae 360000000000000000000000000000000000000000000000000000bbce29a52f *
00000000003c9e4171901fca29a31b9d17739b91a062afe56d8ba2e013810a18 3c0000000000000000000000000000000000000000000000000000bfcf2ed927
0000000000aec5c5b398580b24a1b6afd2a10859e1f36cdf2ac6e93343570eef 040000000000000000000000000000000000000000000000000000c0c4b1a54a *

The lowest X-coordinate I have found is:

000000000000aeea7a7a5c04504f6e4e45452940431c9a264011686f3b746f92

and its private key is:

2000000000000000000000000000000000000000000000000000013a80306e86

Jean_Luc

sr. member

Activity: 462

Merit: 701

If you want a pubkey with a X having more than 90 leading zeros you will need to perform ~2^90 group operation to find it.
The 2 points you mentioned are the privilege of the gui who have chosen G.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Does anybody know how to estimate/calculate the total possible DPs within the range? Moreover, it is also possible that for some DP value there will not be any DPs.

For example, the minimum X-coordinate value I know is for private key 7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0 and for 7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a1
Their X-coordinate has 90 leading zeros, so it is DP=90

Probably there are only 2 X-coordinates with 90 leading zeros, and no more.

Does anybody know some examples with more than 90 leading zeros in x-coordinate with known private keys?

PS. Example above is for (order-1)/2 and for (order-1)/2+1

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: Etar on May 27, 2020, 06:46:14 AM

Quote from: WanderingPhilospher on May 27, 2020, 06:35:15 AM

-snip-
Drop your -dp down to 25 and I'll share my master save file with you. 8.6GB file

if i drop DPbit to 25 nothing will be left from the found points .. I found so far 2^23.57 (expected 2^24.5) (42rtx2080ti)
I will need do job (31-25=6) 2^6=64 time more again. and for DP=25 Expected memory: 60179 MB

My bad. I thought you were starting over from scratch.

Etar

sr. member

Activity: 642

Merit: 316

Quote from: WanderingPhilospher on May 27, 2020, 06:35:15 AM

-snip-
Drop your -dp down to 25 and I'll share my master save file with you. 8.6GB file

if i drop DPbit to 25 nothing will be left from the found points .. I found so far 2^23.57 (expected 2^24.5) (42rtx2080ti)
I will need do job (31-25=6) 2^6=64 time more again. and for DP=25 Expected memory: 60179 MB

Topic: Pollard's kangaroo ECDLP solver - page 122. (Read 59389 times)