Hi all,
Here is my research about using kangaroo methods to solve ECDLP, Part 1.
Open source: https://github.com/RetiredC/Kang-1
This software demonstrates various ways to solve the ECDLP using Kangaroos.
The required number of operations is approximately K * sqrt(range), where K is a coefficient that depends on the method used.
This software demonstrates five methods:
1 - Classic. The simplest method. There are two groups of kangaroos: tame and wild.
As soon as a collision between any tame and wild kangaroos happens, the ECDLP is solved.
In practice, K is approximately 2.10 for this method.
2 - 3-way. A more advanced method. There are three groups of kangaroos: tame, wild1, and wild2.
As soon as a collision happens between any two types of kangaroos, the ECDLP is solved.
In practice, K is approximately 1.60 for this method.
3 - Mirror. This method uses two groups of kangaroos and the symmetry of the elliptic curve to improve K.
Another trick is to reduce the range for wild kangaroos.
In practice, K is approximately 1.30 for this method.
The main issue with this method is that the kangaroos loop continuously.
4 - SOTA. This method uses three groups of kangaroos and the symmetry of the elliptic curve.
In practice, K is approximately 1.15 for this method. The main issue is the same as in the Mirror method.
I couldn’t find any papers about this method, so let's assume that I invented it
5 - SOTA+. This method is the same as SOTA, but also uses cheap second point.
When we calculate "NextPoint = PreviousPoint + JumpPoint" we can also quickly calculate "PreviousPoint - JumpPoint" because inversion is the same.
If inversion calculation takes a lot of time, this second point is cheap for us and we can use it to improve K.
Using cheap point costs only (1MUL+1SQR)/2. K is approximately 1.02 for this method (assuming cheap point is free and not counted as 1op).
Again, I couldn’t find any papers about this method applied to Kangaroo, so let's assume that I invented it.
Important note: this software handles kangaroo looping in a very simple way.
This method is bad for large ranges higher than 100 bits.
Next part will demonstrate a good way to handle loops.
PS. Please don't post any stupid messages here, I will remove them; also don't post AI-generated messages and other spam.
Here is my research about using kangaroo methods to solve ECDLP, Part 1.
Open source: https://github.com/RetiredC/Kang-1
This software demonstrates various ways to solve the ECDLP using Kangaroos.
The required number of operations is approximately K * sqrt(range), where K is a coefficient that depends on the method used.
This software demonstrates five methods:
1 - Classic. The simplest method. There are two groups of kangaroos: tame and wild.
As soon as a collision between any tame and wild kangaroos happens, the ECDLP is solved.
In practice, K is approximately 2.10 for this method.
2 - 3-way. A more advanced method. There are three groups of kangaroos: tame, wild1, and wild2.
As soon as a collision happens between any two types of kangaroos, the ECDLP is solved.
In practice, K is approximately 1.60 for this method.
3 - Mirror. This method uses two groups of kangaroos and the symmetry of the elliptic curve to improve K.
Another trick is to reduce the range for wild kangaroos.
In practice, K is approximately 1.30 for this method.
The main issue with this method is that the kangaroos loop continuously.
4 - SOTA. This method uses three groups of kangaroos and the symmetry of the elliptic curve.
In practice, K is approximately 1.15 for this method. The main issue is the same as in the Mirror method.
I couldn’t find any papers about this method, so let's assume that I invented it
5 - SOTA+. This method is the same as SOTA, but also uses cheap second point.
When we calculate "NextPoint = PreviousPoint + JumpPoint" we can also quickly calculate "PreviousPoint - JumpPoint" because inversion is the same.
If inversion calculation takes a lot of time, this second point is cheap for us and we can use it to improve K.
Using cheap point costs only (1MUL+1SQR)/2. K is approximately 1.02 for this method (assuming cheap point is free and not counted as 1op).
Again, I couldn’t find any papers about this method applied to Kangaroo, so let's assume that I invented it.
Important note: this software handles kangaroo looping in a very simple way.
This method is bad for large ranges higher than 100 bits.
Next part will demonstrate a good way to handle loops.
PS. Please don't post any stupid messages here, I will remove them; also don't post AI-generated messages and other spam.
Been interested about this puzzle for more than a week now; unfortunately I don't have the gear required (I do own two desktops, one i9 14900k with an RTX 2060 and an RTX 2080 and another with i9 10900k with an RTX 3050) and the speeds I got are very good, but won't do much.
Thank you a lot for the work you are doing, I do wonder if you had implemented or found a way to implement this new method? https://arxiv.org/html/2409.08784v1