# 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, 2013 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. Jul 24, 2013 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, 2013 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. Jul 24, 2013 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, 2013 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.)

• In my understanding / mental model, this rejecting and then sampling the final data destroys the randomness. Technically this works for the number (and I would have considered this the most straight forward and simplest way to do the job) but I think as well it destroys/weakens/taints the randomness. Or am I just wrong about that point? Jul 24, 2013 at 18:59
• If the input bits are perfectly random then rejection sampling produces perfectly random outputs. The only loss is that some randomness is "wasted". Jul 24, 2013 at 23:05
• Okay, I just had the same thought after waking up in the morning today. Otherwise it would not have been random anyhow. The only question left is: is a random source that is deemed cryptographically secure such a perfectly random source? Jul 25, 2013 at 7:32
• As my last question is most certainly not answerable, just accepting this as it does at this point answer the question - And that is in both parts. I also had the idea of taking the bit-lane however it does not work for 254 because I need 8 bits for 254 as well, so the second part does it here. Thanks for the nice answer. With the efficiency, you mean this because of data-handling (like doing buffered reads), right? Jul 25, 2013 at 7:46
• 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)$. Jul 26, 2013 at 12:32