Solving ECDLP with Kangaroos: Part 1 + 2 + RCKangaroo

[farou9]

could someone please explain to me what is the relationship between the jumps the kangaroos make or what is the nature of the jump exactly , how does the jumps are made and what makes us soo shore that when they collide on the same point that exact point have something to do with the scalar we are looking for , and from where does start the jumps is it from the interval of the known range of the scalar ?

[atom13]

First I would like to thank the RetiredCoder or (RC). Great work!!!

I'm trying to understand and analyze your code.

I carried out some tests with my 4090 and noticed that e.g. Bit 70 everything works perfectly!

Unfortunately, when I go to bit 130 it looks different, but I'm trying to figure out why there are problems here. Currently I have no idea what the reason(s) are. I'll take a look at the code in a few days. Maybe someone here has the same experiences.

Thanks again :-)

[mitkopasa]

Hi,

Can you add end range to the code? I want to search for narrower ranges.

[RetiredCoder]

RCKangaroo v3.0:

- added "-tames" and "-max" options.
- fixed some bugs.

[zloy_ya]

Hello, thank you very much for your work! Sir, could you also add the -end function to indicate the end of a range? I think many people here would like to break a large range into small ones and go through it)

[RetiredCoder]

Hello, thank you very much for your work! Sir, could you also add the -end function to indicate the end of a range? I think many people here would like to break a large range into small ones and go through it)

Why don't you want to use "-range" for that?

[mitkopasa]

Because I am searching by dividing the whole range into smaller ranges. Even though I used -range option, it does not terminate and continues searching. However, the -max option in V3 can solve this problem. I haven't tried it yet, but I will try, thanks.

Hello, thank you very much for your work! Sir, could you also add the -end function to indicate the end of a range? I think many people here would like to break a large range into small ones and go through it)

Why don't you want to use "-range" for that?

[minobia]

RCKangaroo v3.0:

- added "-tames" and "-max" options.
- fixed some bugs.

Amazing thanks a lot for investing so much of your time in this project so that we can enjoy it!!

[Lolo54]

Very interesting this update, for fun I did the test with a precalculation of the points on #75 bit with -max 3 this already requires 350 Mo of free space.
how many Go available requires for example the precalculation of a 100bit space with -max 10 ?

[minobia]

Very interesting this update, for fun I did the test with a precalculation of the points on #75 bit with -max 3 this already requires 350 Mo of free space.
how many Go available requires for example the precalculation of a 100bit space with -max 10 ?

I did a 85bit -max10 the Generation took 4 hours and 35GB of space

[Lolo54]

Very interesting this update, for fun I did the test with a precalculation of the points on #75 bit with -max 3 this already requires 350 Mo of free space.
how many Go available requires for example the precalculation of a 100bit space with -max 10 ?

I did a 85bit -max10 the Generation took 4 hours and 35GB of space

ok thank you for your answer I'm going to test a 90 in -max 5 to see but I'm not sure I'll have enough space we'll see

[RetiredCoder]

When app starts it displays estimated RAM for DPs based on -range and -dp options, multiply it by -max option to get required RAM (roughly).
Or download latest sources and compile them, I added max RAM size calculation.

[Lolo54]

When app starts it displays estimated RAM for DPs based on -range and -dp options, multiply it by -max option to get required RAM (roughly).
Or download latest sources and compile them, I added max RAM size calculation.

Code:

...RCKangaroo.exe" -dp 16 -range 75 -start 4000000000000000000 -tames rckang75a.dat -max 3
********************************************************************************
*                    RCKangaroo v3.0  (c) 2024 RetiredCoder                    *
********************************************************************************

This software is free and open-source: https://github.com/RetiredC
It demonstrates fast GPU implementation of SOTA Kangaroo method for solving ECDLP
Windows version
CUDA devices: 1, CUDA driver/runtime: 12.6/12.6
GPU 0: NVIDIA GeForce RTX 2070, 8.00 GB, 36 CUs, cap 7.5, PCI 1, L2 size: 4096 KB
Total GPUs for work: 1

TAMES GENERATION MODE

Solving point: Range 75 bits, DP 16, start...
SOTA method, estimated ops: 2^37.702, RAM for DPs: 0.315 GB. DP and GPU overheads not included!
Max allowed number of ops: 2^39.287
Estimated DPs per kangaroo: 2.891. DP overhead is big, use less DP value if possible!
GPU 0: allocated 3477 MB, 1179648 kangaroos. OldGpuMode: Yes
GPUs started...
GEN: Speed: 1149 MKeys/s, Err: 0, DPs: 216K/3410K, Time: 0d:00h:00m/0d:00h:03m
GEN: Speed: 1582 MKeys/s, Err: 0, DPs: 467K/3410K, Time: 0d:00h:00m/0d:00h:02m
GEN: Speed: 1566 MKeys/s, Err: 0, DPs: 701K/3410K, Time: 0d:00h:00m/0d:00h:02m
GEN: Speed: 1552 MKeys/s, Err: 0, DPs: 935K/3410K, Time: 0d:00h:00m/0d:00h:02m
GEN: Speed: 1542 MKeys/s, Err: 0, DPs: 1168K/3410K, Time: 0d:00h:00m/0d:00h:02m
GEN: Speed: 1538 MKeys/s, Err: 0, DPs: 1402K/3410K, Time: 0d:00h:01m/0d:00h:02m
GEN: Speed: 1533 MKeys/s, Err: 0, DPs: 1636K/3410K, Time: 0d:00h:01m/0d:00h:02m
GEN: Speed: 1532 MKeys/s, Err: 0, DPs: 1871K/3410K, Time: 0d:00h:01m/0d:00h:02m
GEN: Speed: 1523 MKeys/s, Err: 0, DPs: 2104K/3410K, Time: 0d:00h:01m/0d:00h:02m
….
GEN: Speed: 1519 MKeys/s, Err: 0, DPs: 9282K/3410K, Time: 0d:00h:06m/0d:00h:02m
GEN: Speed: 1521 MKeys/s, Err: 0, DPs: 9515K/3410K, Time: 0d:00h:06m/0d:00h:02m
GEN: Speed: 1519 MKeys/s, Err: 0, DPs: 9749K/3410K, Time: 0d:00h:07m/0d:00h:02m
GEN: Speed: 1519 MKeys/s, Err: 0, DPs: 9983K/3410K, Time: 0d:00h:07m/0d:00h:02m
GEN: Speed: 1519 MKeys/s, Err: 0, DPs: 10217K/3410K, Time: 0d:00h:07m/0d:00h:02m
Operations limit reached
Stopping work ...
saving tames...
tames saved

I must not have understood correctly but in this case the ram displayed is indeed 0.315GB and -max 3 it should take 900 MB or even 1 GB but it took 352 MB exactly 352055KB, why? 

[RetiredCoder]

I must not have understood correctly but in this case the ram displayed is indeed 0.315GB and -max 3 it should take 900 MB or even 1 GB but it took 352 MB exactly 352055KB, why? 

Because there is some fixed RAM size required to store table itself (about 200MB):

Code:

if (gMax > 0)
{
MaxTotalOps = gMax * ops;
double ram_max = (32 + 4 + 4) * MaxTotalOps / dp_val; //+4 for grow allocation and memory fragmentation
ram_max += sizeof(TListRec) * 256 * 256 * 256; //3byte-prefix table
ram_max /= (1024 * 1024 * 1024); //GB
printf("Max allowed number of ops: 2^%.3f, max RAM for DPs: %.3f GB\r\n", log2(MaxTotalOps), ram_max);
}

[Lolo54]

yes it is perfectly clear now ok thank you and congratulations again for your work and sharing it is impressive ! I hope you find #135, you deserve it sincerely

[atom13]

I had time again and was able to continue taking tests.
I think there is a bug in the tool when solving large bit areas.

I was able to solve bits 70, 75, and 80 without any problems, but from 85 onwards none of the puzzles that had already been solved. For example, I changed values ​​at Bit 85 start, etc. but it was never found. An example, after that i stop -> Err: 0, DPs: 98481K/77175K, Time: 0d:00h:13m/0d:00h:10m

Don't think I'm making a mistake because it solved bit 70, 75, 80. If I had time again I would look at it more intensively, I'm not sure but maybe there is an overflow, .....
Can someone else please test this too??

[WanderingPhilospher]

I had time again and was able to continue taking tests.
I think there is a bug in the tool when solving large bit areas.

I was able to solve bits 70, 75, and 80 without any problems, but from 85 onwards none of the puzzles that had already been solved. For example, I changed values ​​at Bit 85 start, etc. but it was never found. An example, after that i stop -> Err: 0, DPs: 98481K/77175K, Time: 0d:00h:13m/0d:00h:10m

Don't think I'm making a mistake because it solved bit 70, 75, 80. If I had time again I would look at it more intensively, I'm not sure but maybe there is an overflow, .....
Can someone else please test this too??

Please, it is better to send the command line you are / were using. That way someone can take a better look at everything. Maybe you forgot to use the correct subtract amount, wrong key, etc. Could be anything, could be nothing, but it's the first thing to look at.

[RetiredCoder]

It takes a lot of time to confirm K at higher ranges.
For v3.0 I did tests for "-range 89 -dp 22": I started 12 instances of RCKangaroo on 12 4090 (one GPU per one instance to get larger path for kangaroos), solved 133 points in total with average K=1.21.
For range 100 I did the same and just waited for two points solved so at least it can solve it, though I cannot confirm exact K because it would take a couple of weeks.


One more piece of science! 
Everybody knows that when we calculate "NextPoint = PreviousPoint + JumpPoint", we can also quickly calculate "PreviousPoint - JumpPoint" because the inversion is the same.
Therefore, if the inversion calculation takes a lot of time, this second point is cheap for us, and we can use it to improve K.
I updated Part #1: Added "SOTA+" method with K = 1.02.

[moderator's note: consecutive posts merged]

[minobia]

[INFO] Found existing Tames file: C:\RCKangaroo\v1\tames85.dat
[INFO] Processing higher bits: 0/1125899906842623
[INFO] Executing command for high offset: 0
[DEBUG] Command: powershell -Command "& \"C:\\RCKangaroo\\v1\\RCKangaroo.exe\" -range 85 -start 0 -dp 16 -pubkey 02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16 -tames \"C:\RCKangaroo\v1\tames85.dat\""
********************************************************************************
*                    RCKangaroo v3.0  (c) 2024 RetiredCoder                    *
********************************************************************************

This software is free and open-source: https://github.com/RetiredC
It demonstrates fast GPU implementation of SOTA Kangaroo method for solving ECDLP
Windows version
CUDA devices: 1, CUDA driver/runtime: 12.6/12.6
GPU 0: NVIDIA GeForce RTX 4080 SUPER, 15.99 GB, 80 CUs, cap 8.9, PCI 59, L2 size: 65536 KB
Total GPUs for work: 1

MAIN MODE

Solving public key
X: 145D2611C823A396EF6712CE0F712F09B9B4F3135E3E0AA3230FB9B6D08D1E16
Y: 667A05E9A1BDD6F70142B66558BD12CE2C0F9CBC7001B20C8A6A109C80DC5330
Offset: 0000000000000000000000000000000000000000000000000000000000000000

Solving point: Range 85 bits, DP 16, start...
SOTA method, estimated ops: 2^42.702, RAM for DPs: 4.253 GB. DP and GPU overheads not included!
Estimated DPs per kangaroo: 222.050.
load tames...
tames loaded
GPU 0: allocated 1501 MB, 491520 kangaroos. OldGpuMode: No
GPUs started...

The actual DPs (1176754K) far exceed the expected DPs (109142K), meaning the solver is generating significantly more DPs than anticipated.
The more i lower the DP bits from 16 the worse it gets, it does not generate a single Solved Point.

Anyone ?

MAIN: Speed: 5242 MKeys/s, Err: 0, DPs: 1280854K/109142K, Time: 0d:00h:39m/0d:00h:22m
MAIN: Speed: 5242 MKeys/s, Err: 0, DPs: 1281650K/109142K, Time: 0d:00h:40m/0d:00h:22m
MAIN: Speed: 5197 MKeys/s, Err: 0, DPs: 1282445K/109142K, Time: 0d:00h:40m/0d:00h:22m
MAIN: Speed: 5242 MKeys/s, Err: 0, DPs: 1283247K/109142K, Time: 0d:00h:40m/0d:00h:22m
MAIN: Speed: 5194 MKeys/s, Err: 0, DPs: 1284042K/109142K, Time: 0d:00h:40m/0d:00h:22m
MAIN: Speed: 5193 MKeys/s, Err: 0, DPs: 1284838K/109142K, Time: 0d:00h:40m/0d:00h:22m
MAIN: Speed: 5242 MKeys/s, Err: 0, DPs: 1285640K/109142K, Time: 0d:00h:40m/0d:00h:22m
MAIN: Speed: 5193 MKeys/s, Err: 0, DPs: 1286435K/109142K, Time: 0d:00h:41m/0d:00h:22m
MAIN: Speed: 5194 MKeys/s, Err: 0, DPs: 1287228K/109142K, Time: 0d:00h:41m/0d:00h:22m
MAIN: Speed: 5242 MKeys/s, Err: 0, DPs: 1288031K/109142K, Time: 0d:00h:41m/0d:00h:22m
MAIN: Speed: 5193 MKeys/s, Err: 0, DPs: 1288825K/109142K, Time: 0d:00h:41m/0d:00h:22m
MAIN: Speed: 5242 MKeys/s, Err: 0, DPs: 1289619K/109142K, Time: 0d:00h:41m/0d:00h:22m
MAIN: Speed: 5197 MKeys/s, Err: 0, DPs: 1290422K/109142K, Time: 0d:00h:41m/0d:00h:22m
MAIN: Speed: 5197 MKeys/s, Err: 0, DPs: 1291217K/109142K, Time: 0d:00h:42m/0d:00h:22m
MAIN: Speed: 5193 MKeys/s, Err: 0, DPs: 1292011K/109142K, Time: 0d:00h:42m/0d:00h:22m
MAIN: Speed: 5197 MKeys/s, Err: 0, DPs: 1292813K/109142K, Time: 0d:00h:42m/0d:00h:22m
MAIN: Speed: 5242 MKeys/s, Err: 0, DPs: 1293608K/109142K, Time: 0d:00h:42m/0d:00h:22m
MAIN: Speed: 5242 MKeys/s, Err: 0, DPs: 1294403K/109142K, Time: 0d:00h:42m/0d:00h:22m
MAIN: Speed: 5197 MKeys/s, Err: 0, DPs: 1295206K/109142K, Time: 0d:00h:42m/0d:00h:22m
MAIN: Speed: 5242 MKeys/s, Err: 0, DPs: 1296000K/109142K, Time: 0d:00h:43m/0d:00h:22m
MAIN: Speed: 5193 MKeys/s, Err: 0, DPs: 1296794K/109142K, Time: 0d:00h:43m/0d:00h:22m
MAIN: Speed: 5242 MKeys/s, Err: 0, DPs: 1297596K/109142K, Time: 0d:00h:43m/0d:00h:22m
MAIN: Speed: 5197 MKeys/s, Err: 0, DPs: 1298390K/109142K, Time: 0d:00h:43m/0d:00h:22m
MAIN: Speed: 5194 MKeys/s, Err: 0, DPs: 1299185K/109142K, Time: 0d:00h:43m/0d:00h:22m
MAIN: Speed: 5193 MKeys/s, Err: 0, DPs: 1299980K/109142K, Time: 0d:00h:43m/0d:00h:22m

[RetiredCoder]

The actual DPs (1176754K) far exceed the expected DPs (109142K), meaning the solver is generating significantly more DPs than anticipated.
The more i lower the DP bits from 16 the worse it gets, it does not generate a single Solved Point.

For solving points with saved tames you must use same "-range" and "-dp" values that you used for tames generation.