Pollard Rho

[SatoshiNakamotoBitcoins]

Hello Mon'Ami from beautiful France...;-)

I was curious what the ETA of your new and promissing project Pollard Rho will be...

Like to learn from you.

Sincères salutations

[JeanLucPons]

Hi, Still huge professional work. No free time at the moment.

[fernand77]

really looking forward to when you have free time to use the project to carry out the Pollard rho please make soft for brute-force bitcoin addresses

[fernand77]

reference to an algorithm for solving an ECDLP that claims to have subexponential time. There, in the presentation, some formulas are not very clear, but it is clear that Semaev’s Polynomials is a component of the algorithm.

---

There is also another version of brute force - RIX-ECDLP, which is here, in this book, there is info. It assumes brute force, with the calculation of only X coordinates of points, through inversions, without Y coordinates, which accelerates brute force by 10-20%.

But it would be more expedient to concentrate efforts on the development of a parallel version of the pollard-rho-algorithm for solving the ECDLP described in the article here: habr.com/ru/post/335906/ There, inside the article, the method "Turtle and Hare, based on finding the Floyd cycle, and finding the private key behind O (√n). But this method does not seem to be parallel.

If you just decide to program this variant of the algorithm, "Turtle and Hare", then with n = 2 ^ 256, √n = 2 ^ 128 combinations it will be about the maximum that you agree, much better than 2 ^ 160 for all values ​​of ripemd160.

There is also a certain "muddy for me" method of the Pollard-rho algorithm called kangaroo, or how it is also indexed - the pollard-rho lambda-algorithm. I could not google the sources, workers. The article describes the algorithm for the usual DLP, but in my opinion, there is a modification of it for the ECDLP. But, it says here that this method can work in a range of values, and somewhere else I saw that the ECDLP decides for O (√ (a-b)), where a is the desired value of the private key, b is the initial value, in the range for its search. So, this lambda-method, kangaroo method, Pollard-rho algorithm for ECDLP, it can be parallelized, and on video cards to count. And maybe even optimize. I think if you go through the whole thing, and understand how it works, then you can write a software similar to this one, yours, with the same parallelism, either for CUDA or for OpenCL.

More effective than the variations of the Pollard algorithm ("Turtle and Hare", as well as "parallel kangaroo"), for sure may be implementation of a variation of the Shore Algorithm modified solution ECDLP, but for its execution we need quantum computers ... There is a bit of information about this algorithm in that article, and here it is.

he pollard rho method "turtle and hare" also requires O (√n) operations somewhere , but O (1) memory . Already better, because when n = 2 ^ 256, √n = 2 ^ 128, and so many points must be saved initially, before comparison, in the "baby step giant step" algorithm. These are not bytes, these are exactly points. For this preservation - no memory of the planet is enough. And then another 2 ^ 128 iterations - which is also a lot .

you can parallelize the "baby step giant step" and specify the range to search for, but as I understand it, you can also specify a range in the lambda algorithm (kangaroo algorithm), although this method is a modification of the pollard- algorithm rho, which is less memory sensitive than the "baby step giant step".

But if we consider this algo on Semaev's polynomials, which claims to be sub-exponential, then it should work much faster, and in a much smaller number of iterations. Well, if you delve into the essence of the principles of its work, you will surely find that, due to the determinism of the algorithm, it can also be distributed, specifying different ranges for the search. Yes, and more ... Judging by the values ​​of X-coordinates of points on an elliptic curve in a finite field, it can be seen that they are repeated at opposite points. These points are in different semigroups of an abelian group. That is, in one of the semigroups, the x-coordinates of the points are unique, as in the second semigroup, but the order of these x-coordinates is reverse. So, if you see the group of points generated by the 2G generator point, you can see that the first semigroup of this group contains all points that have even k coefficients in the group of points generated by G, and the second semigroup of 2G contains all odd points of G. However, entirely and completely, the group of points of an elliptic curve generated by a point 2G, it completely coincides with a group of points of a curve generated by a point G. If one could somehow generate one of the SEMIGROUP points of 2G, and check whether a point from the group G belongs to this SEMIGROUP, then one could definitely say that the coefficient is even at a point of the group G, or odd. Then, it would be possible to divide a point by two (multiplying by a multiplicative inversion of two modulo n) using multi-multiplicative and additive inversions, or remove G (adding it with a point, backward G), and then divide it by two, and thus a sequence of subtracting-halving — to arrive at the generator point G, restoring itself by the sequence of operations — the key k, corresponding to the public key kG, and thereby solving the ECDLP. But to check the belonging of points, it is possible only for the entire curve (for the whole group of points of this curve), substituting its coordinates into the equation of the elliptic curve itself, but is it possible, and how can I generate a SEMIGROUP, and even more so, is it possible, and how - check whether the point belongs to the HALF-LINE, it is not clear. In appearance, even and odd points in a group are no different.

If it were possible to check whether a point belongs to a semigroup, then to understand whether its coefficient is even or odd, it would be enough not to go deep into the group generated by 2G, and consider only the main group of points generated by G. In this case, whose parity is unknown, is first divided by two (multiplication by a multiplicative inversion of two modulo n). Further, there are two options: either the even point, and the result of the division is necessarily contained in the first semigroup, or the odd point, and the result of the division is necessary, in the second semigroup.

Then, checking whether a half point result belongs to any semigroup of G, one could definitely say whether the coefficient is even at the original point or odd. Well, then, already, after an unequivocal determination of the parity-oddness of the point coefficient, one could: either divide it into two, or take away G, and then divide it into two, and so with a sequence of operations, come to G, extracting the bits of the private key k from the initial kG, and all - intermediate results.

---

Perhaps this information will help you. Pollard's Rho method for ECDLP on CUDA devices Parallel Pollard Rho Factorize an integer as fast as possible using the Pollard's Rho algorithm

[fernand77]

@JeanLucPons please read this post https://bitcointalk.org/index.php?topic=1306983.msg51785368#msg51785368

[fernand77]

Yes, we really miss such a tool (software). Unfortunately, not everyone knows programming well. I also hope that @JeanLucPons will do something to share with people. There is nothing here to hide this ...

[Spacebar76]

Some people already have Pollard Kangaroo, but they don’t want to share it. I hope that Jean-Luc will help us. https://imgur.com/a/f3zTmTa

[fernand77]

@JeanLucPons You have high hopes =) you are a very smart person, we will be grateful to you

[JeanLucPons]

Hi, No much time at the moment to work on an optimized of pollard rho. It is not possible to determine the parity of a point (they're is not know method in polynomial time/space) otherwise ECDLP would be feasible.

[fernand77]

Here is what I found: https://catalog.lib.kyushu-u.ac.jp/opac_download_md/1434304/p145.pdf Subexponential algorithm, sort of like. Can you program it? Nice your translated article here: https://habr.com/ru/post/335906/

Wanted to add next...

Baby-step-giant-step can working with k points in memory, and m=n/k iterations, because for Q=dP each d can be writted as km+x, where x∈[0, k], k - number of points after baby-steps, m - multiplier for brute-force. When k = √n, then m = n/k = n/(√n) = √n, so O(√n) for Baby-step-giant-step. But, k can be lesser, and searching m=n/k in range [0, m] can be parallelized, using specified diapasons.

For Pollard-rho algorithm Brent method is faster than Floyd by 30-40 percent. Also, there is birthday paradox.

Points can be subtracted and divided. Q - P = Q + (-P), where -P is additive inverse of P. P(x, y) = -P(x, (-y mod p)) Q/2 = Q modular_multiplicative_inverse(2, n) Q/k = Q modular_multiplicative_inverse(k, n)

When odd point divided at 2, then the result there is in the second semigroup of the group the points on elliptic curve in finite field. Maybe, if the semigroup can be generated, and point exitsting there can be verified, then it will be possible to determine uniquely the parity of d, and the coefficients for all another points, and if Q = d*P, and d is even, then Q/2, else if d is odd - (Q-P)/2, and check parity of result again and again, and extract bits of d.

[ghost]

https://bitcointalk.org/index.php?action=profile;u=961392

[neutron220]

Hi. https://github.com/pikachunakopika/Pollard_s-kangaroo

SCAM, do not buy