[Cryptography] Mapping numbers to permutations
Viktor Dukhovni
cryptography at dukhovni.org
Thu Dec 4 17:48:00 EST 2014
On Thu, Dec 04, 2014 at 04:21:03PM -0500, Jerry Leichter wrote:
[ Sorry about my "Reply-To", your message went to the list. ]
> 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,
No, when I was considering the case that N is odd. So 6 is not
covered. For N even a sufficiently large power $N^k$ is divisible
by $2^m$ and one is then able to output $m$ unbiased bits (though
the mapping is certainly not one-to-one if N has odd factors).
> 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.
That's the case I was proving, N is odd.
> 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.)
We are on the same page.
--
Viktor.
More information about the cryptography
mailing list