kangaroo-wild with precomputed (and chosen) DP

[arulbero]

I wanted to know how fast a normal pc with a normal amount of RAM and without a GPU can retrieve a key in a short range like 2^74 - 2^75.

So I implemented a my version of the kangaroo algorithm:  https://github.com/arulbero/kangaroo-wild  

Code:

gcc -O3 -march=native -falign-functions=32 -falign-loops=32 kangaroo_wild.c G_stub.c -o kangaroo_wild -pthread -lm -flto

On my laptop (Alder Lake 12th Gen Intel(R) Core(TM) i7-12700H): it takes about 3s for each key.

It is a bit faster if I search multiple keys in parallel.

The program can retrieve a key in higher range (like 2^77 - 2^78 or  2^80 - 2^81) as well based on the same database.

Size of the database : 6GB.

[dextronomous]

hi there arulbero,

the 2nd file is not available anymore, could you help out,
thanks for this another master piece

[arulbero]

hi there arulbero,

the 2nd file is not available anymore, could you help out,
thanks for this another master piece

Now it should work.

[dextronomous]

hi there arulbero,

the 2nd file is not available anymore, could you help out,
thanks for this another master piece

Now it should work.

./kangaroo_wild extend 037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc 79 80
[PARAMS] V2 loaded: local=12 jump=9 hist=4 esc=128 mult=2000 min_dp=1 trunc=11
[PARAMS] GLOBAL_BITS=16 RANGE=74-75 DIST_BYTES=8 TRUNC_BITS=11
[PARAMS] scored_target_dp=268435456 seed=42 local_buf1=64
[PARAMS] q_hat=0.428733 R_factor=1.1 N_sel=536870912
[JUMP_TABLE] target_dp=268435456 gap=3.52e+13 opt=137438953472 (2^37.0)
====================================================
[DB] 4194304.00 KB | 536870912 entries (disk: 8 B/entry, dist:8, trunc:11)
[FP] Fingerprints: 2097152.00 KB (536870912 entries)
[BO] Bucket offsets: 16384.00 KB (HASH_INDEX_BITS=22, u32)
====================================================
--- KANGAROO WILD ---
[CONFIG] Range: 2^74 - 2^75 | GLOBAL_BITS: 16 | DIST_BYTES: 8 | TRUNC_BITS: 11
[CONFIG] Workers: 60 | Batch: 20 | C: 1200 | VITA: 4194304

[EXTEND] Range 2^79 - 2^80 | DB 2^74 - 2^75 | 32 partitions

[KEY 1/1] Searching (extend 2^79-2^80, 32 parts): 037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc
[EXTEND 1/1] 140.2M steps | 46.5M/s | 3s elapsed
[EXTEND 1/1] 313.2M steps | 52.0M/s | 6s elapsed
[EXTEND 1/1] 523.3M steps | 58.0M/s | 9s elapsed
[EXTEND 1/1] 789.1M steps | 65.6M/s | 12s elapsed
[EXTEND 1/1] 1143.2M steps | 76.1M/s | 15s elapsed
[EXTEND 1/1] 1609.9M steps | 89.3M/s | 18s elapsed
[EXTEND 1/1] 2126.0M steps | 101.1M/s | 21s elapsed
[EXTEND 1/1] 2667.9M steps | 111.0M/s | 24s elapsed

[!!!] KEY FOUND (f2 m1/1 delta=710 partition=26): 0x61a5c66dcc11b5ad180
[SOLVED 1/1] Key: 0xea1a5c66dcc11b5ad180 (part 26) | Steps: 2862.9M | Time: 25.133s

============================================================
           STEP ACCOUNTING REPORT
============================================================
 Total steps:               2862.87M
------------------------------------------------------------
 BREAKDOWN:
   life_limit rsp:                0
   buf1 (cycle) rsp:              2
   escape rsp:                    0
   escape jumps:            6866748
   avg life at rsp:         1780856
------------------------------------------------------------
 DP STATS:
   DP global hits:            43611
   DP filtered (k):               0
   DP saved:                      0
 WILD STATS:
   DP checked vs DB:          43611
   DB matches:                    1
============================================================

[!!!] PRIVATE KEY: 0xea1a5c66dcc11b5ad180

wow did not expected this one,
thought on extend parallel and or do we get saved dps or tames or wilds in this one or is it needed just to ask, what
to edit for this besides the 23 you did, and or threads or batch, after compiling the file it does not take in the -b and or -w just
keeps the settings from the file, no problem btw,

[arulbero]

thought on extend parallel and or do we get saved dps or tames or wilds in this one or is it needed just to ask, what
to edit for this besides the 23 you did, and or threads or batch, after compiling the file it does not take in the -b and or -w just
keeps the settings from the file, no problem btw,

I removed the -w - b options because the program runs slower.

I just update the program and the flag of compiler.

I'm working on a new version of the db, time to retrieve a key: -25%

On my pc these are the results with the new database:

- sequential search :  2.2 seconds for each key (16 workers, 20 batch_k, 74-75 bit range)
- parallel search : 1.1 seconds for each key (16 workers, 60 batch_k, 74-75 bit range)
- parallel search: 46 seconds for each key (16 workers, 60 batch_k, 80-81 bit range)

On AWS (c8id.metal-48xl instance, 96 core 3.9 GHz, 2 thread for each core):

- sequential search: 0.46 seconds for each key (192 workers, 20 batch_k, 74-75 bit range)
- parallel search: 0.072 seconds for each key (192 workers, 60 batch_k, 74-75 bit range)
- parallel search: 6 seconds for each key (192 workers, 60 batch_k, 80-81 bit range)
- parallel search: about 45 seconds for each key (192 workers, 60 batch_k, 84-85 bit range)

[dextronomous]

can't wait to test that one to, thanks for explaining showing the details,
what would be the best setting to setup this code for the 135th puzzle,

[samee2026]

I wanted to know how fast a normal pc with a normal amount of RAM and without a GPU can retrieve a key in a short range like 2^74 - 2^75.

So I implemented a my version of the kangaroo algorithm:  https://github.com/arulbero/kangaroo-wild


On my laptop (Alder Lake 12th Gen Intel(R) Core(TM) i7-12700H): it takes about 3s for each key.

It is a bit faster if I search multiple keys in parallel.

The program can retrieve a key in higher range (like 2^77 - 2^78 or  2^80 - 2^81) as well based on the same database.

Size of the database : 6GB.

Git link not work, some one share new link    or upload full git + compile file use https://gofile.io

@arulbero why deleted git ?

[arulbero]

can't wait to test that one to, thanks for explaining showing the details,
what would be the best setting to setup this code for the 135th puzzle,

I wanted to know how fast a normal pc with a normal amount of RAM and without a GPU can retrieve a key in a short range like 2^74 - 2^75.

This program is only for the short range 2^74-2^75 and for a few bits more (like 80 or 84).

It doesn't make sense trying to resolve the 135th puzzle with a cpu, gpus are way more fast.  

Only in this short range "cpu with the database of the precomputed dp" is like (more or less) to "a gpu"

At the moment the program can search to 2**74 * (2**12) = 2**74 * 4096 = 2**86 - 2**87 range:

Code:

 
#define MAX_PARTITIONS 4096   // supports up to 12 extra bits over DB range

if you want to search in the 2**100 - 2**101 range:

Code:

#define MAX_PARTITIONS (1ULL << 26)   // supports up to 26 extra bits over DB range

26 means that it takes 2^26 times more than time to 2^74-75 range, let's say it takes 1s on 2^74-75,

are you sure you want to wait 2^26 seconds = 2 years?

Git link not work, some one share new link    or upload full git + compile file use https://gofile.io

@arulbero why deleted git ?

I didn't delete anything, the link is ok.

*********************************************************************************

EDIT: Database updated! Enjoy the speedup!

[samee2026]

Git link not work, some one share new link    or upload full git + compile file use https://gofile.io

@arulbero why deleted git ?

I didn't delete anything, the link is ok.

*********************************************************************************

EDIT: Database updated! Enjoy the speedup!

i was share my screenshot https://pikwy.com/web/69b16f7b158aa71c200dd2ad  . you can see "404 this is not the page you are looking for"

what happen i cant see git
someone help to download this git files https://github.com/arulbero/kangaroo-wild
thankyou

[arulbero]

Git link not work, some one share new link    or upload full git + compile file use https://gofile.io

@arulbero why deleted git ?

I didn't delete anything, the link is ok.

*********************************************************************************

EDIT: Database updated! Enjoy the speedup!

i was share my screenshot https://pikwy.com/web/69b16f7b158aa71c200dd2ad  . you can see "404 this is not the page you are looking for"

what happen i cant see git
someone help to download this git files https://github.com/arulbero/kangaroo-wild
thankyou

You are right, there is a problem with my github account, I uploaded the code + DB files here:   https://gofile.io/d/9af4a6a1-ae82-43a7-9cf1-a1374e39e040

To compile:
 
gcc -O3 -march=native -falign-functions=32 -falign-loops=32 kangaroo_wild.c G_stub.c -o kangaroo_wild -pthread -lm -flto

[oddstake]

Indeed , your version is faster than keyhunt bsgs .

Puzzle 75 - Time: 0.216s

Code:

❯ ./kangaroo_wild -w 384 -b 20 single 03726b574f193e374686d8e12bc6e4142adeb06770e0a2856f5e4ad89f66044755
[PARAMS] V2 loaded: local=12 jump=9 hist=4 esc=128 mult=2000 min_dp=1 trunc=11
[PARAMS] GLOBAL_BITS=16 RANGE=74-75 DIST_BYTES=8 TRUNC_BITS=11
[PARAMS] scored_target_dp=268435456 seed=42 local_buf1=64
[PARAMS] q_hat=0.428733 R_factor=1.1 N_sel=536870912
[JUMP_TABLE] target_dp=268435456 gap=3.52e+13 opt=137438953472 (2^37.0)
====================================================
[DB] 4194304.00 KB | 536870912 entries (disk: 8 B/entry, dist:8, trunc:11)
[HUGEPAGE] 8.00 GB on 1GB hugepages (8 pages)
[DB] Loaded tame DB (8192 MB) [HUGEPAGE]
[HUGEPAGE] 2.00 GB on 1GB hugepages (2 pages)
[FP] Fingerprints: 2048.00 MB (536870912 entries) [HUGEPAGE]
[BO] Bucket offsets: 16384.00 KB (HASH_INDEX_BITS=22, u32)
====================================================
--- KANGAROO WILD ---
[CONFIG] Range: 2^74 - 2^75 | GLOBAL_BITS: 16 | DIST_BYTES: 8 | TRUNC_BITS: 11
[CONFIG] Workers: 384 | Batch: 20 | C: 7680 | VITA: 8388608
[CONFIG] Latency overhead: 2264.92M steps (4.5*C*D) — reduce -b if too high

[KEY 1/1] Searching: 03726b574f193e374686d8e12bc6e4142adeb06770e0a2856f5e4ad89f66044755

[!!!] KEY FOUND (f2 m1/1 delta=1077 partition=0): 0x4c5ce114686a1336e07
[SOLVED 1/1] Key: 0x4c5ce114686a1336e07 | Steps: 180.0M | Time: 0.216s

============================================================
           STEP ACCOUNTING REPORT
============================================================
 Total steps:                180.01M
------------------------------------------------------------
 BREAKDOWN:
   life_limit rsp:                0
   buf1 (cycle) rsp:              0
   escape rsp:                    0
   escape jumps:             176006
------------------------------------------------------------
 DP STATS:
   DP global hits:             2689
   DP filtered (k):               0
   DP saved:                      0
 WILD STATS:
   DP checked vs DB:           2689
   DB matches:                    1
============================================================

[!!!] PRIVATE KEY: 0x4c5ce114686a1336e07

Puzzle 80 - Time: 1.016s

Code:

❯ ./kangaroo_wild -w 384 -b 20 extend 037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc 79 80
[PARAMS] V2 loaded: local=12 jump=9 hist=4 esc=128 mult=2000 min_dp=1 trunc=11
[PARAMS] GLOBAL_BITS=16 RANGE=74-75 DIST_BYTES=8 TRUNC_BITS=11
[PARAMS] scored_target_dp=268435456 seed=42 local_buf1=64
[PARAMS] q_hat=0.428733 R_factor=1.1 N_sel=536870912
[JUMP_TABLE] target_dp=268435456 gap=3.52e+13 opt=137438953472 (2^37.0)
====================================================
[DB] 4194304.00 KB | 536870912 entries (disk: 8 B/entry, dist:8, trunc:11)
[HUGEPAGE] 8.00 GB on 1GB hugepages (8 pages)
[DB] Loaded tame DB (8192 MB) [HUGEPAGE]
[HUGEPAGE] 2.00 GB on 1GB hugepages (2 pages)
[FP] Fingerprints: 2048.00 MB (536870912 entries) [HUGEPAGE]
[BO] Bucket offsets: 16384.00 KB (HASH_INDEX_BITS=22, u32)
====================================================
--- KANGAROO WILD ---
[CONFIG] Range: 2^74 - 2^75 | GLOBAL_BITS: 16 | DIST_BYTES: 8 | TRUNC_BITS: 11
[CONFIG] Workers: 384 | Batch: 20 | C: 7680 | VITA: 8388608
[CONFIG] Latency overhead: 2264.92M steps (4.5*C*D) — reduce -b if too high

[EXTEND] Range 2^79 - 2^80 | DB 2^74 - 2^75 | 32 partitions

[KEY 1/1] Searching (extend 2^79-2^80, 32 parts): 037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc

[!!!] KEY FOUND (f2 m1/1 delta=1445 partition=26): 0x61a5c66dcc11b5ad180
[SOLVED 1/1] Key: 0xea1a5c66dcc11b5ad180 (part 26) | Steps: 945.4M | Time: 1.016s

============================================================
           STEP ACCOUNTING REPORT
============================================================
 Total steps:                945.37M
------------------------------------------------------------
 BREAKDOWN:
   life_limit rsp:                0
   buf1 (cycle) rsp:              0
   escape rsp:                    0
   escape jumps:             974948
------------------------------------------------------------
 DP STATS:
   DP global hits:            14445
   DP filtered (k):               0
   DP saved:                      0
 WILD STATS:
   DP checked vs DB:          14445
   DB matches:                    1
============================================================

[!!!] PRIVATE KEY: 0xea1a5c66dcc11b5ad180

Puzzle 85 - Time: 118.365s

Code:

❯ ./kangaroo_wild -w 384 -b 20 extend 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a 84 85
[PARAMS] V2 loaded: local=12 jump=9 hist=4 esc=128 mult=2000 min_dp=1 trunc=11
[PARAMS] GLOBAL_BITS=16 RANGE=74-75 DIST_BYTES=8 TRUNC_BITS=11
[PARAMS] scored_target_dp=268435456 seed=42 local_buf1=64
[PARAMS] q_hat=0.428733 R_factor=1.1 N_sel=536870912
[JUMP_TABLE] target_dp=268435456 gap=3.52e+13 opt=137438953472 (2^37.0)
====================================================
[DB] 4194304.00 KB | 536870912 entries (disk: 8 B/entry, dist:8, trunc:11)
[HUGEPAGE] 8.00 GB on 1GB hugepages (8 pages)
[DB] Loaded tame DB (8192 MB) [HUGEPAGE]
[HUGEPAGE] 2.00 GB on 1GB hugepages (2 pages)
[FP] Fingerprints: 2048.00 MB (536870912 entries) [HUGEPAGE]
[BO] Bucket offsets: 16384.00 KB (HASH_INDEX_BITS=22, u32)
====================================================
--- KANGAROO WILD ---
[CONFIG] Range: 2^74 - 2^75 | GLOBAL_BITS: 16 | DIST_BYTES: 8 | TRUNC_BITS: 11
[CONFIG] Workers: 384 | Batch: 20 | C: 7680 | VITA: 8388608
[CONFIG] Latency overhead: 2264.92M steps (4.5*C*D) — reduce -b if too high

[EXTEND] Range 2^84 - 2^85 | DB 2^74 - 2^75 | 1024 partitions

[KEY 1/1] Searching (extend 2^84-2^85, 1024 parts): 0329c4574a4fd8c810b7e42a4b398882b381bcd85e40c6883712912d167c83e73a
[EXTEND 1/1] 2984.9M steps | 990.0M/s | 3s elapsed
[EXTEND 1/1] 5957.7M steps | 990.2M/s | 6s elapsed
[EXTEND 1/1] 8929.2M steps | 990.2M/s | 9s elapsed
[EXTEND 1/1] 11898.8M steps | 990.0M/s | 12s elapsed
[EXTEND 1/1] 14862.2M steps | 989.5M/s | 15s elapsed
[EXTEND 1/1] 17821.9M steps | 988.9M/s | 18s elapsed
[EXTEND 1/1] 20776.7M steps | 988.3M/s | 21s elapsed
[EXTEND 1/1] 23727.2M steps | 987.7M/s | 24s elapsed
[EXTEND 1/1] 26674.0M steps | 987.0M/s | 27s elapsed
[EXTEND 1/1] 29617.0M steps | 986.4M/s | 30s elapsed
[EXTEND 1/1] 32555.4M steps | 985.7M/s | 33s elapsed
[EXTEND 1/1] 35490.9M steps | 985.1M/s | 36s elapsed
[EXTEND 1/1] 38420.5M steps | 984.4M/s | 39s elapsed
[EXTEND 1/1] 41345.2M steps | 983.7M/s | 42s elapsed
[EXTEND 1/1] 44266.3M steps | 983.0M/s | 45s elapsed
[EXTEND 1/1] 47180.9M steps | 982.2M/s | 48s elapsed
[EXTEND 1/1] 50094.3M steps | 981.6M/s | 51s elapsed
[EXTEND 1/1] 53006.2M steps | 980.9M/s | 54s elapsed
[EXTEND 1/1] 55915.6M steps | 980.3M/s | 57s elapsed
[EXTEND 1/1] 58822.5M steps | 979.7M/s | 60s elapsed
[EXTEND 1/1] 61722.5M steps | 979.1M/s | 63s elapsed
[EXTEND 1/1] 64620.4M steps | 978.5M/s | 66s elapsed
[EXTEND 1/1] 67529.9M steps | 978.1M/s | 69s elapsed
[EXTEND 1/1] 70470.1M steps | 978.2M/s | 72s elapsed
[EXTEND 1/1] 73431.1M steps | 978.5M/s | 75s elapsed
[EXTEND 1/1] 76394.0M steps | 978.8M/s | 78s elapsed
[EXTEND 1/1] 79354.1M steps | 979.1M/s | 81s elapsed
[EXTEND 1/1] 82310.0M steps | 979.3M/s | 84s elapsed
[EXTEND 1/1] 85259.2M steps | 979.4M/s | 87s elapsed
[EXTEND 1/1] 88201.3M steps | 979.5M/s | 90s elapsed
[EXTEND 1/1] 91137.0M steps | 979.4M/s | 93s elapsed
[EXTEND 1/1] 94069.9M steps | 979.3M/s | 96s elapsed
[EXTEND 1/1] 96998.8M steps | 979.2M/s | 99s elapsed
[EXTEND 1/1] 99924.0M steps | 979.1M/s | 102s elapsed
[EXTEND 1/1] 102845.7M steps | 978.9M/s | 105s elapsed
[EXTEND 1/1] 105762.6M steps | 978.7M/s | 108s elapsed
[EXTEND 1/1] 108674.3M steps | 978.5M/s | 111s elapsed
[EXTEND 1/1] 111583.8M steps | 978.3M/s | 114s elapsed
[EXTEND 1/1] 114490.3M steps | 978.0M/s | 117s elapsed

[!!!] KEY FOUND (f1 m1/1 delta=1507 partition=92): 0x60c4f018d51b8cebba8
[SOLVED 1/1] Key: 0x11720c4f018d51b8cebba8 (part 92) | Steps: 115695.3M | Time: 118.365s

============================================================
           STEP ACCOUNTING REPORT
============================================================
 Total steps:             115695.29M
------------------------------------------------------------
 BREAKDOWN:
   life_limit rsp:             7679
   buf1 (cycle) rsp:              8
   escape rsp:                    0
   escape jumps:          468223050
   avg life at rsp:         8375788
------------------------------------------------------------
 DP STATS:
   DP global hits:          1726878
   DP filtered (k):               0
   DP saved:                      0
 WILD STATS:
   DP checked vs DB:        1726878
   DB matches:                    1
============================================================

[!!!] PRIVATE KEY: 0x11720c4f018d51b8cebba8

[arulbero]

Indeed , your version is faster than keyhunt bsgs .

....

Thanks.

Note: the kangaroo algorithm is probabilistic, to have a real measure you need to test at least 1000 keys to get "a mean time".

And to have a better time with different keys I think it is better 384 x 60 instead of 384 x 20.  118s is too much for 85 bit, my average time is 65s (and 1s for 80 bit is too low), you should get under 40s (mean time) for 85 bit, and median time usually is even better.
 
For 80 bit you should get around 3s (or maybe "your" cores are faster than mine?)

85 bit should be about 2^5 = 32 times 80 bit, not 120 times.

This is the readme file:

Code:

gcc -O3 -march=native -falign-functions=32 -falign-loops=32 kangaroo_wild.c G_stub.c -o kangaroo_wild -pthread -lm -flto

[oddstake]

Ok, I've done some tests, here are my results.

 Workers: 384 | Batch: 60

Code:

[GEN_TEST_EXT] Generating 100 random public keys in range 2^74 - 2^75 ...
[GEN_TEST_EXT] Written 100 keys to public_keys.txt

==========================================================
   SUMMARY
==========================================================
   Total keys:     100
   Solved:         100
   Failed/Aborted: 0
   Total time:     46.9s
   Min:            0.104s | Max: 1.005s
   Mean time/key:  0.469s
   >>> MEDIAN:     0.405s <<<
   Mean steps/key: 556.58M
   Median steps:   470.83M
   StdDev:         276.67M
   95% CI (mean):  [502.35M, 610.81M] steps/key
==========================================================




[GEN_TEST_EXT] Generating 50 random public keys in range 2^79 - 2^80 ...
[GEN_TEST_EXT] Written 50 keys to public_keys.txt

==========================================================
   SUMMARY
==========================================================
   Total keys:     50
   Solved:         50
   Failed/Aborted: 0
   Total time:     141.5s
   Min:            0.511s | Max: 6.914s
   Mean time/key:  2.830s
   >>> MEDIAN:     2.562s <<<
   Mean steps/key: 4439.05M
   Median steps:   4201.68M
   StdDev:         2647.07M
   95% CI (mean):  [3705.32M, 5172.78M] steps/key
==========================================================



[GEN_TEST_EXT] Generating 30 random public keys in range 2^84 - 2^85 ...
[GEN_TEST_EXT] Written 30 keys to public_keys.txt


==========================================================
   SUMMARY
==========================================================
   Total keys:     30
   Solved:         30
   Failed/Aborted: 0
   Total time:     1998.6s
   Min:            2.215s | Max: 260.319s
   Mean time/key:  66.621s
   >>> MEDIAN:     42.331s <<<
   Mean steps/key: 109071.49M
   Median steps:   69956.94M
   StdDev:         110963.58M
   95% CI (mean):  [69363.69M, 148779.30M] steps/key
==========================================================

[arulbero]

Ok, I've done some tests, here are my results.

 Workers: 384 | Batch: 60

Code:

[GEN_TEST_EXT] Generating 100 random public keys in range 2^74 - 2^75 ...
[GEN_TEST_EXT] Written 100 keys to public_keys.txt

==========================================================
   SUMMARY
==========================================================
   Total keys:     100
   Solved:         100
   Failed/Aborted: 0
   Total time:     46.9s
   Min:            0.104s | Max: 1.005s
   Mean time/key:  0.469s
   >>> MEDIAN:     0.405s <<<
   Mean steps/key: 556.58M
   Median steps:   470.83M
   StdDev:         276.67M
   95% CI (mean):  [502.35M, 610.81M] steps/key
==========================================================




[GEN_TEST_EXT] Generating 50 random public keys in range 2^79 - 2^80 ...
[GEN_TEST_EXT] Written 50 keys to public_keys.txt

==========================================================
   SUMMARY
==========================================================
   Total keys:     50
   Solved:         50
   Failed/Aborted: 0
   Total time:     141.5s
   Min:            0.511s | Max: 6.914s
   Mean time/key:  2.830s
   >>> MEDIAN:     2.562s <<<
   Mean steps/key: 4439.05M
   Median steps:   4201.68M
   StdDev:         2647.07M
   95% CI (mean):  [3705.32M, 5172.78M] steps/key
==========================================================



[GEN_TEST_EXT] Generating 30 random public keys in range 2^84 - 2^85 ...
[GEN_TEST_EXT] Written 30 keys to public_keys.txt


==========================================================
   SUMMARY
==========================================================
   Total keys:     30
   Solved:         30
   Failed/Aborted: 0
   Total time:     1998.6s
   Min:            2.215s | Max: 260.319s
   Mean time/key:  66.621s
   >>> MEDIAN:     42.331s <<<
   Mean steps/key: 109071.49M
   Median steps:   69956.94M
   StdDev:         110963.58M
   95% CI (mean):  [69363.69M, 148779.30M] steps/key
==========================================================

30/50 keys -> too much variance, if you do these tests again probably you will get very different results.

You should get around 3s for 80 bit and around 50s (maybe, I'm not 100% sure) for 85 bit. Do tests with 1000 keys each.

[oddstake]

I got the idea, more tests , less variance.
If anyone interested, here is my tames generation script which works with your kangaroo_wild.
Maybe a lot of things to do and make it better.

https://github.com/providiu/tames-gen/

It might be not fully functional but to get an ideea about tames generations.
Also requires a modified version of kangaroo_wild.c

[oddstake]

Hunting for puzzles with CPU is a dead end anyway.

[arulbero]

Hunting for puzzles with CPU is a dead end anyway.

I never said that this program is about finding 135 key,

it is about 74-80 bit range search on normal pc without gpu.

If you can access to a pc with 192 cores / 192 thread you can use it to search 85-90 bit, but the db is build and optimized for the 74-75 range.

[oddstake]

To generate a DB 77 it take about 12 days and also a lot of RAM and SSD space needed.

Code:

 ./tame_phase -n 2147483648 -r 76 77 -g 16 -w 360 -b 20 --scored
============================================================
  TAME PHASE - Scored DP Database Generator
============================================================
  Range:          2^76 - 2^77
  Global bits:    16 (DP mask: 0xffff)
  Target DPs:     2147483648 (2147.5M)
  Scored mode:    YES
  Workers:        360 x 20 = 7200 kangaroos
  Jump table:     512 entries (bits=9, seed=42)
  Escape table:   128 entries (mult=2000)
  History:        4
  Local buf1:     1024
  Vita (life):    8388608
  Dist bytes:     10 (trunc=0)
  Hash index:     28 bits (268435456 buckets)
  Prefix:         77_scored_16
  Midpoint:       0x18000000000000000000
============================================================
[INIT] Building jump table...
[JUMP_TABLE] target_dp=2147483648 gap=1.76e+13 opt=68719476736 (2^36.0)
[INIT] Allocating hash table: 17179869184 slots (512.00 GB)
[HUGEPAGE] 512.00 GB on 1GB hugepages (512 pages)
[RUN] Starting 360 workers...
[CHECKPOINT] Auto-save every 30 minutes to 77_scored_16_checkpoint.bin
[PROGRESS] DPs: 32003 / 6442450944 (0.0%) | 419.08M steps/s | 6372 DP/s | fill: 0.0% | ETA: 1011016s | elapsed: 5s
[PROGRESS] DPs: 63554 / 6442450944 (0.0%) | 418.75M steps/s | 6310 DP/s | fill: 0.0% | ETA: 1020972s | elapsed: 10s
[PROGRESS] DPs: 95131 / 6442450944 (0.0%) | 418.60M steps/s | 6315 DP/s | fill: 0.0% | ETA: 1020120s | elapsed: 15s
[PROGRESS] DPs: 126638 / 6442450944 (0.0%) | 418.52M steps/s | 6301 DP/s | fill: 0.0% | ETA: 1022381s | elapsed: 20s
[PROGRESS] DPs: 158692 / 6442450944 (0.0%) | 418.47M steps/s | 6411 DP/s | fill: 0.0% | ETA: 1004931s | elapsed: 25s
[PROGRESS] DPs: 190407 / 6442450944 (0.0%) | 418.43M steps/s | 6343 DP/s | fill: 0.0% | ETA: 1015669s | elapsed: 30s
[PROGRESS] DPs: 222019 / 6442450944 (0.0%) | 418.39M steps/s | 6322 DP/s | fill: 0.0% | ETA: 1018973s | elapsed: 35s

[arulbero]

To generate a DB 77 it take about 12 days and also a lot of RAM and SSD space needed.

Code:

 ./tame_phase -n 2147483648 -r 76 77 -g 16 -w 360 -b 20 --scored
============================================================
  TAME PHASE - Scored DP Database Generator
============================================================
  Range:          2^76 - 2^77
  Global bits:    16 (DP mask: 0xffff)
  Target DPs:     2147483648 (2147.5M)
  Scored mode:    YES
  Workers:        360 x 20 = 7200 kangaroos
  Jump table:     512 entries (bits=9, seed=42)
  Escape table:   128 entries (mult=2000)
  History:        4
  Local buf1:     1024
  Vita (life):    8388608
  Dist bytes:     10 (trunc=0)
  Hash index:     28 bits (268435456 buckets)
  Prefix:         77_scored_16
  Midpoint:       0x18000000000000000000
============================================================
[INIT] Building jump table...
[JUMP_TABLE] target_dp=2147483648 gap=1.76e+13 opt=68719476736 (2^36.0)
[INIT] Allocating hash table: 17179869184 slots (512.00 GB)
[HUGEPAGE] 512.00 GB on 1GB hugepages (512 pages)
[RUN] Starting 360 workers...
[CHECKPOINT] Auto-save every 30 minutes to 77_scored_16_checkpoint.bin
[PROGRESS] DPs: 32003 / 6442450944 (0.0%) | 419.08M steps/s | 6372 DP/s | fill: 0.0% | ETA: 1011016s | elapsed: 5s
[PROGRESS] DPs: 63554 / 6442450944 (0.0%) | 418.75M steps/s | 6310 DP/s | fill: 0.0% | ETA: 1020972s | elapsed: 10s
[PROGRESS] DPs: 95131 / 6442450944 (0.0%) | 418.60M steps/s | 6315 DP/s | fill: 0.0% | ETA: 1020120s | elapsed: 15s
[PROGRESS] DPs: 126638 / 6442450944 (0.0%) | 418.52M steps/s | 6301 DP/s | fill: 0.0% | ETA: 1022381s | elapsed: 20s
[PROGRESS] DPs: 158692 / 6442450944 (0.0%) | 418.47M steps/s | 6411 DP/s | fill: 0.0% | ETA: 1004931s | elapsed: 25s
[PROGRESS] DPs: 190407 / 6442450944 (0.0%) | 418.43M steps/s | 6343 DP/s | fill: 0.0% | ETA: 1015669s | elapsed: 30s
[PROGRESS] DPs: 222019 / 6442450944 (0.0%) | 418.39M steps/s | 6322 DP/s | fill: 0.0% | ETA: 1018973s | elapsed: 35s

From 74-75  to 76-77 you need to recover 2 bits:  or you pass from 2GB+4GB to 2GB+16GB, or you pass to 2GB + 8GB and from 16 global bits to 17 global bits

and in the tame phase you can exploit all the power of your pc:  384 x 256 --> 2.2 G steps/s

[oddstake]

I will try to generate a DB 77 but it will take a lot of time. I will let you know when finishes and made some tests.