Topic: Pollard's kangaroo ECDLP solver - page 80. (Read 58563 times)

OK could give me your input file and how you launched the program ?
Lots of dead kangaroos usually means that you search for a key which is out of the specified range.

Ah...this google translator over 6 million dead kangaroo appeared while solving the problem with DP13, I solved the problem using the -t 4 processor if it matters.


PS. I didn't modify the code.

What do you mean by "adding 6 million kangaroos dead" ?
Did you modify the code ?

It happened when solving the problem with DP 13, I also wanted to add with over 6 million kangaroos dead.

The problem occurred in v2.1

This should not happen. Which release is producing wrong collisions and in which cases (merging work file, basic usage, ..) ?


The expected number of operation is the average number of group operations needed to solve the key (including the DP overhead). It correspond to ~50% probability.
If you use -m 3 and if the search is aborted, you are sure at ~99.7% that the key is not in the given range.

Could someone explain to me why this happened?

Could someone tell me how to set the parameter -m ? And what does 'expected operations' number mean?
On the plot in github I see that there is chance like +- 99% when the number of group operations is 6*sqrt(n).
If for example program shows 'Expected operations: 2^44.10', when may I assume there is no result? 2^44.10? 2^45? Sooner, later?

Hi,

I published a new release 2.2:
https://github.com/JeanLucPons/Kangaroo/releases/tag/2.2

Slight performance increase:
    ModInv performance increase (Thanks to Peter Dettman)
    GPU kernel performance increase

Thanks to gmaxwell for pointing me out this interesting PR of bitcoin core

Pollard's method can only search for those addresses where the public key is known. So the answer to your question is Yes.

Right.

This is specific to disk stored distinguished points stored for tame entries used to generically accelerate many different executions.

The idea is that sometimes distinguished points are closely spaced on a walk, and sometimes far apart. Given a constant amount of storage you would prefer to store widely spaced distinguished points over closely spaced ones.  You can't know the actual spacing, since you don't know what the walk looked like before your start-- but you could track how far you walked and store that.

I won't implement a rho method for secp256k1. It is not feasible to reach a solution using this method.


Thanks for the reading. I didn't read it yet.
I suppose that when you speak of walk length, you mean the total number of jumps of the walk, not the total traveled distance.
The problem of storing length of walk is that on GPU access to global memory is very slow. I will see if I manage to improve things.

I haven't seen this paper discussed here: https://cr.yp.to/dlog/cuberoot-20120919.pdf

There are a number of good points in it but particularly the point of generating *better* distinguished points by preferentially keeping ones that have longer walk lengths is interesting.

@Jean_Luc, implement please Pollard's RHO code to bitcoin

Maybe you can make a Pollard RHO like Pollard Kangaro without memory cost



This is a link to sources:



Code Sources ready to go - CUDA demonstration using Pollard's Rho  - https://github.com/dghost/factor-cuda

https://github.com/dghost

BSGS and Pollard's rho both cost O(n−−√) operations where n is the order of the group, typically a >250-bit integer as in edwards25519, secp256k1, nistp256, etc. However, BSGS also has O(n−−√) memory cost, so the area*time cost—which is a proxy for euro or joule cost—is O(n) even if we unrealistically assume O(1) random access to memory. In contrast, Pollard's rho costs O(n−−√) time on a machine of constant space and thus O(n−−√) area*time. Pollard's rho can also be naturally parallelized to trade space for time without increasing the overall cost. There are also some small optimizations that apply to Pollard's rho for elliptic curves, but they only change the constant factors a little; it remains O(n−−√)
.
If you knew the secret scalar were in a restricted range [a,b]
, you could use Pollard's kangaroo, which costs O(b−a−−−−√) time on a machine of constant size. The kangaroo method too can be parallelized without increasing overall cost. If, say, b−a≈2100 for your secp256k1 target, then this would be within reach for you while none of the above methods would be feasible. But it would be surprising for anyone to choose a scalar restricted enough that Pollard's kangaroo finds it substantially faster than rho.

so everybody seraching higher known addresses ?

[EDITED]

I must rethink it ;-)

Address 64 has no outgoing transactions.Therefore, the public key is unknown.

If pubkey to 64 was exposed it would have been solved already.

Hi all,

So no one knows a pubkey to 64?

For continuous range you could divide a_i by 's': a_i/s = a₀/s + i.