1. Hash the private key
2. "Clamp" the result
3. Multiply by the base point
Clearly step 1 will give you an equal chance of any 5-byte prefix, so the question is whether steps 2 and 3 preserve that entropy.
The clamping in step 2 does two things: it clears the 3 least-significant bits (making the value divisible by 8) and it sets the 2 most-significant bits to 01. So we've lost 5 bits of entropy here.
Finally, step 3 multiplies the value by the base point. The base point is a pair of large (255 bit) numbers. Multiplying by it probably does not appreciably reduce entropy, but I could be wrong here.
So I think your brute-forcing is probably not in vain. However, I would certainly start by trying to generate all possible 2-byte prefixes, 3-byte prefixes, etc. to gain some confidence there no "unreachable" prefixes.
EDIT: I was able to verify that all 2-byte and 3-byte prefixes are reachable. I strongly suspect that that all 5-byte prefixes are reachable as well.
I would certainly start by trying to generate all possible 2-byte prefixes, 3-byte prefixes, etc.
OK great, I did try that to get some insight as to whether various 2/3/4-byte series at different index positions would show up... and they did. The relative lack of results by adding that 5th byte had me concerned, but figured it's due to the exponentially-decreasing odds.
I'll have to read more on what you mean by #2/3. Clamping / bit entropy and the more intricate math is where I start to get lost. This seems like a good resource:
The clamping in step 2 does two things: it clears the 3 least-significant bits (making the value divisible by 8) and it sets the 2 most-significant bits to 01. So we've lost 5 bits of entropy here.
Finally, step 3 multiplies the value by the base point. The base point is a pair of large (255 bit) numbers. Multiplying by it probably does not appreciably reduce entropy, but I could be wrong here.
So I think your brute-forcing is probably not in vain. However, I would certainly start by trying to generate all possible 2-byte prefixes, 3-byte prefixes, etc. to gain some confidence there no "unreachable" prefixes.
EDIT: I was able to verify that all 2-byte and 3-byte prefixes are reachable. I strongly suspect that that all 5-byte prefixes are reachable as well.