samr7,
Is it possible for you to comment a little on what the difficulty number represents and how it's calculated. I tried looking thru the code and figuring it out but BN math and probability is definitely not my forte. I ended up being pretty confused.
I'd like to be able to estimate the probability for a prefix pattern in my own code without running vanitygen - if not perfect mathematically then a rough time estimate would work.
Hi BkkCoins,
Difficulty is the number of keys that have to be checked, on average, to find a match.
The simplest way to do this is to have a table of prefix difficulties, and for each character after the beginning of the prefix, multiply by 58. For this, you'd have something like:
11 = 256
12-1P = 22
1Q = 65
1R-1z = 1353
So, 1Abc = 22 x 58 x 58 = 74008, and 1egg = 1353 x 58 x 58 = 4551492, which are very close to the exact difficulties. This scheme wouldn't be very accurate for multiple leading 1s, and certain suffixes of 1Q, without special handling of those cases.
The exact, but more complicated way to do this is to follow the formula:
Difficulty = (Total addresses) / (Matching addresses)
The tricky part is figuring out the number of matching addresses. If your keys were 10-digit base-10 numbers, and you wanted to find everything with a prefix of 12345, with no leading 0s, then:
Total keys = 10000000000
Matches = 1234500000 ... 1234599999 = 100000 total matches
Difficulty = 10000000000 / 100000 = 100000, or 1:100000 keys
It's more complex to do this for base-58, but as in the example, the task is to convert a base-58 prefix into ranges of numbers that result in matches. If you're interested, I will post more about this.