# Calculate entropy of modified base32 hash

I am trying to develop a scheme for generating unique (probable within bounds) ids in a distributed application. I want the id to be easily remembered, easily spoken, and easily read. I chose base32 as the encoding method, as it gives a large set of characters, universally recognised, and without confusion between similar looking characters.

So, if I have a set of 32 characters, and an id of length 4, I have $32^4$ (1048576) permutations, so the chance of a collision when a new id is created is something like one in 32^4/total-existing-ids - which is too much of a chance.

I think $32^6$ is reasonable as a trade off between memorability, and chance of collision, but it is harder to remember and read 6 random base32 characters.

I find it much easier, if all the numbers and letters are grouped, so where it might have been e4hu8a I find ehua48 much easier to remember/read/speak. Or k3c5f0 as kcf350.

So, finally, my question...

How much entropy do I lose by my scheme of rearranging totally random base32 strings so letters come before numbers (but remain in the original order amongst themselves)?

How can I calculate the entropy for different length strings using this method?

• I am also interested in totally different approach to what I am trying to achieve. Nothing is set in stone yet, not even base32. – Billy Moon Nov 4 '13 at 22:14
• Collision probability is relatively easy to calculate, you have $(1-\frac 1{2^{20}})^n$ probability of success for $n$ existing unique IDs using your original $32^4$ setup. Note that if you have a collision, you have the option of "trying again". What is the (rough) estimate of IDs you are expecting within your ID space? Up to $100000$ entries, I calculate a $90$% chance of no collision... – abiessu Nov 4 '13 at 22:36
• @abiessu: you are missing the birthday paradox. If you have $n$ ids, you have $\frac {n^2}2$ pairs, so the chance of a collision exceeds $50\%$ with far fewer ids. – Ross Millikan Nov 4 '13 at 22:43
• @RossMillikan: Gah, the birthdays! I always forget that one... – abiessu Nov 4 '13 at 22:44

This answer assumes you use all $36$ letters and numbers. I don't know how many letters and numbers are among the $32$. You should be able to update it to reflect your alphabet.
To calculate the entropy, you just need to calculate the number of ids and take the base 2 log. If there are six letters, you have $26^6=308,915,776$ ids. To get the number with numbers included, note that the number with five letters and a number is $\frac {10}{26}$ of that, so the total is $26^6\sum_{i=0}^6 \left(\frac{10}{26}\right)^i=26^6\frac{1-(\frac{10}{26})^7}{1-\frac{10}{26}}\approx 5E8$ The base $2$ log of this is about $28.9$. This should be compared with $\log_2 36^6 \approx 31.0$, so you are losing about $2.1$ bits of entropy. I assumed you always have letters before numbers. You can reduce this a bit if you allow both orders of numbers and letters.