Good afternoon Alberto:

I have been studying BSGS, and Pollard's Kangaroo methods for a while now. I have made an observation trying to mix BSGS with the Kangaroo method that I believe could be helpful.

I have figured out you can use the concept of distinguished points used in the kangaroo method to improve BSGS.

Here is a simple example of what I have observed:

One of the big restraints in the BSGS is the available memory to store the database, each X coordinate you calculate (every jump or every step you make) goes against the database. The other big restraint is that each point has a lookup cost against the database. (1 Point = 1 search). I understand you use a bloom filter in your program to make the search on the database a lot faster and make the database as small as possible in order to fit in the RAM available.

Here is my idea: what about if you store only distinguished points in the database, this means only X coordinates with an amount of N leading zeroes. This has 3 big benefits, one, you can discard all the points that does not have N leading zeroes on the fly, with a very small cost. Second, only compare against the database the small X coordinates. Third, you will store less bits per X coordinates.

This will improve the speed of the algorithm because you will make the same amount of comparisons but most of them only discarding the bigger X's, and then compare only the small X coordinates not discarded.

The other big benefit is that your database won't be restrained anymore by RAM, instead use RAM to store only the distinguished points found and in a latter step, compare against a big stored database in a server. 

The draw-back is that you will spend more point computations building the database, but this is made only once.

By example a very simple case:

Case 1:
You set a database of 1024 X coordinates (baby steps), you can jump a distance of 2048 (because of symmetry) and each jump has to be compared using the bloom filter.
Cost : 1 jump of distance 2024 = 1 database search

Case 2:
You set N to be 8 bits, so you store only the X coordinates beginning with 8 leading zero bits. You search for the first 1024 distinguished points, with a mean search size of 256 points per distinguished point. To make the database, you have to search 1024*256 = 262.144 points to get the 1024 distinguished points needed. Now you can make  jumps of  262.144 * 2 = 524.288 (2 **19), and search for the next distinguished point after landing ( one very big jump, many small jumps).  You make the first jump 2**19, then find the next distinguished point ( with a step of one), then jump 2**19 again. On each step you discard the big X coordinates, and keep only the small X's, this small ones are the only you need to compare. So the mean jump length on average is the same (2**19/256) = 2048, but you only made 256 comparisons on average against the first byte of the coordinate ( a very small lookup cost) and stored temporarily only one small X coordinate that will be later compared against the database.

cost : To build the database calculate 2**18 points, then for 1 jump average 2024 distance = 1  leading zeroes comparison + 1/256 database search.

I 'm trying this idea using a slightly modified version of "Bitcrack", but it has been difficult for me because I'm new at cuda programming.

Does your implementation of the bloom filter takes this observation in to consideration?

Do you think this is a good idea?

Thanks