Quote from: albert0bsd on April 22, 2023, 08:34:38 PM

Well yes it is some offtopic but i going to reply to you here

Okay, I didn't get your idea at first glance, but after rereading it for the second time, I now understand what you're trying to do.

There are many substractions in BSGS not only ONE example:

Current Implementation:

Code:

Key 99
known range 75-100
Baby step 5 = { 0,1,2,3,4}
Giant step 5 = {0,5,10,25,20}

First subtraction to move key to the BSGS range
99(key) - 75(Base range) = 24

New Target Key 24

Giant step 0
24 - 0 = 24 is on Baby Table? NO

Giant step 1
24 - 5 = 19 is on Baby Table? NO

Giant step 2
24 - 10 = 14 is on Baby Table? NO

Giant step 3
24 - 15 = 9 is on Baby Table? NO

Giant step 4
24 - 20 = 4 is on Baby Table? YES (HIT)

Calcualted KEY is Giant Step 4 plus Baby step 4 PLUS [b]Base range[/b], this is 20 + 4 + 75 = 99

Your proposed Implementation:

Code:

Key 99
known range 75-100
Baby step 5 = {75,76,77,78,79}
Giant step 5 = {0,5,10,25,20}
Target Key 99

Giant step 0
99 - 0 = 99 is on Baby Table? NO

Giant step 1
99 - 5 = 94 is on Baby Table? NO

Giant step 2
99 - 10 = 89 is on Baby Table? NO

Giant step 3
99 - 15 = 84 is on Baby Table? NO

Giant step 4
99 - 20 = 79 is on Baby Table? YES (HIT)

Calcualted KEY is the HIT key

I don't know if that is your idea or not, please correctme if im wrong But in this example We only avoid one substraction, all the Giant Step subtractions remain... There will be some more varians of this (only make stride
with the Giant step, etc...) but almost all keep the Giant Step subtractions.

BTW another important thing to Generate a lis from 1 to X is that we can use that SAME list for ANOTHER targets BUt if you do the list from Target to ( Target + X), then that list only is going to be useful againts that specific target.

Mora about BSGS: https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/

You are right, I was wrong. I just think of it in my head and I'm aware of trade off, creating new list with every target but when you put it with example I see it clearly useless.

There something I found odd that could be useful for this topic, I test both KeyHunt-Cuda & VanitySearch, there result is too big different in the speed.
KeyHunt-Cuda(I test on around 20M keys, so with one key it should be 2200-2400Mk/s)
[00:00:04] [CPU+GPU: 2151.32 Mk/s] [GPU: 2151.32 Mk/s] [C: 0.000000 %] [R: 0] [T: 8,606,711,808 (34 bit)] [F: 0]

VanitySearch
[5258.87 Mkey/s][GPU 5258.87 Mkey/s][Total 2^36.89][Prob 0.0%][50% in 42.0213y][Found 0]

I know VanitySearch is just check first few bits of the address but that could be useful trade off for example checking 70% of the address to increase the speed of keyhunt and if there are a hit then do 100% checking.