I've been looking at generating some vanity addresses today, and I found it surprising that the program generating the address predicts that it will take a different amount of tries to compute a vanity address of the same length, but with a different pattern. For example, generating "11..." takes 256 tries, while "12..." takes 23. Shouldn't it takes the same amount of tries to generate both of them, or am I missing some important detail?
Each leading 1 in an address after the first 1 represents a leading zero byte in the 160 bit hash of the public key, and so makes the search 256 times harder. See the wiki page for Base58Check encoding for details. Whereas any other character makes the search only around 56 times harder.
Every version 0 bitcoin address begins with a 1. And 1 in 256 of them begin with two 1's. However, I don't know where the 23 comes from. Perhaps it's a result of Benford's law - we're changing to base 58, and so can expect more addresses to start with '12' than any other 2 characters.
To see this, suppose there were 256 addresses, from 0x00 to 0xFF, and that we converted them to base 10 to make addresses. There are 256 different addresses, and 111 of the 256 begin with a '1' (1, 10, 11, ..., 19, 100, 101, ..., 199). In bitcoin's base58 encoding, value 1 is encoded by character '2'.
Edit: the above is kind of convincing until you see that:
- '12' through '16' all have difficulty 23,
- '17' through '1P' have difficulty 22,
- '1Q' has difficulty 65 and
- '1R' through '1z' have difficulty 1353.