# Bitarithmetrics to Base X

I've got the following theoretical problem which puzzles me a bit:

I can obtain a string of n bytes (as octets, one byte = one octet = eight bits) of random data. I need to preserve the randomness while reducing the base from 256 to x where x is below 256 (and not 0, 1, 2, 4, 8, 16, 32, 64 or 128).

As I want to preserve the randomness, I don't want to cut-off (waste) any information from this string until I've obtained the number of chunks I need. This is for reason of randomness which can be a limited resource on the computer.

I had the idea to do this for base64 which is simple because I can just create 4 numbers out of a single byte (by shifting bits for example: encode64()). But how to do with a base like 254 for example? I can not cut off at bit-boundaries here, can I?

Do I probably need to create a number large enough out of base 2 based bits that can contain both bases? (This is one of the ideas I have so far).

Would be great to get some feedback, I normally paint pictures with such problems, however, just discovered this website here yesterday and I normally use Stackoverflow so I thought I give it a try :D

If you're interested in some non-theoretical background to my question, see "What is the meaning of the term “simple string” for the SALT string in Unix crypt using SHA-256 and SHA-512?", you might get an idea why I don't want to loose any information bits from the random source.

• I'm not sure I understood the question but why don't you normalize your string? Something like you receive $m$ then you return $\lfloor m\cdot \frac{x}{256}\rfloor$. Anyway you will loose some informations when you convert to a smaller basis. – wece Jul 24 '13 at 13:59
• I don't want to loose information otherwise this is a simple floating-point/floor operation which is not what I'm looking for. – hakre Jul 24 '13 at 14:25
• If your random variable can take 256 values and you want to encode it with less than 8 bits then you will loose informations no matter what you do. – wece Jul 24 '13 at 14:48
• @wece: I know about base64 implementation using 256 value sources, just making four out of one. No information is lost. And that's with less thatn 8 bits as well, so what you write sounds pretty short. – hakre Jul 24 '13 at 15:32
• Do you? I was pretty sure that information theory stated that you can't. But may be I'm wrong and may be I didn't get what you mean by loss of information (or by bits may be). – wece Jul 24 '13 at 16:25

You can use "arithmetic decoding". Interpret your random data as a random bit stream which encodes a random number between $0$ and $1$. Then write this number in base $B$.
A much simpler method is "rejection sampling". Suppose for example that $128 < B < 256$. Given a random byte $x$, if $0 \leq x < B$ then output $x$, otherwise reject. If $x$ is close to $256$ then this is pretty efficient. (To get higher efficiency, try the same trick with some power of $B$, i.e. output several digits at once.)
• No, you can always do arithmetic decoding. Check out the Wikipedia article on arithmetic encoding. The basic idea is that your stream of bits encodes a number in $[0,1)$. If the number $Z$ falls in $[x/254,(x+1)/254)$, then you decode $x$ and continue with $254(Z-x/254)$. – Yuval Filmus Jul 26 '13 at 12:32