[Cryptography] Mapping numbers to permutations

[Jerry Leichter]

[Just to you]
I'm not sure exactly what you're trying prove, but if it's the statement "Given a generator for values uniformly distributed in {0, N-1}, where N is not a power of 2, generating a bit stream either discards some values or may wait indefinitely before outputting anything" is false.  Take N=6.  If the generated value n is in {0, 3}, use it to generate two bits.  Otherwise, use n-4 as a single bit.  This works for any even number - what you're doing is generating bits for every 1 in the binary representation of N.  In the special case where there is only a single 1 bit - i.e., a power of two - you can always generate exactly that many bits.

This doesn't work when N is odd and it's interesting to see what happens:  You pull off values by powers of two and are finally left with only a single possible value, which doesn't give you even one bit of output.  I agree with you that in this case, you're stuck.  Using the trick above, you only have to throw out one possible value - and by thinking of k outputs of the N-value generator as a k-bit base N number, you can make the chance of having to throw away a value decrease exponentially with k.  So the probability of being forced to wait indefinitely can cheaply be made exponentially small - but I agree that it can't be eliminated.

The reverse argument is, I think, stronger:  Given an unbiased bit stream, producing an unbiased choice of from {0, N-1} without the possibility of infinite waiting seems to only be possible when N is a power of 2.  (Here, the simple counting argument works:  You can't possibly use all states of the input, and you *might* get an infinite stream of "skipped" states.)

                                                        -- Jerry


-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4813 bytes
Desc: not available
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20141204/db63ea21/attachment.bin>