[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:

> 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.
```