[Cryptography] Mapping numbers to permutations
Jerry Leichter
leichter at lrw.com
Thu Dec 4 16:21:03 EST 2014
[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>
More information about the cryptography
mailing list