Double speed for BSGS #19
Description
Hi every one, hi JLP i hope you read this.
Current approach for BSGS is more o less the, example:
Target Key 99
known range 75-100 (Like puzzles etc...)
Baby step 5 = { 0,1,2,3,4}
Giant step 5 = {0,5,10,15,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
Here we covered from 0 to 25
But since negative Numbers have the same X value of positive numbers that mean that our current baby table is also valid for:
Baby step 5 = {-4,-3,-2,-1,0,1,2,3,4}
We can move exclude the 0 for this example and keep some table like:
Baby step 5 = {-5,-4,-3,-2,-1,1,2,3,4,5}
We can handle the Zero element in some especial case, or include it and use an odd baby table,
So to work with this new Baby table we need to rearange the Giant steps just a litle.
Giant step 5 = {5,15,25,35,45}
| GS | RANGE BS |
| 5 | 0 - 10 |
| 15 | 10 - 20 |
| 25 | 20 - 30 |
| 35 | 30 - 40 |
| 45 | 40 - 50 |
So we covered a Double Range from 0 to 50 with the same number of Operations, this is double speed.
I already implement this on my tool keyhunt.