[Cryptography] Mapping numbers to permutations
ab at bri-c.de
Thu Dec 4 01:28:25 EST 2014
> Now here is an insight new to me, though someone else has probably
> already had it. This is also a bijective way to convert bases in the
> output of nonbinary deterministic PRNG's to binary. Let's say you have
> a deterministic bit generator based on a permutation of 5 elements which
> produces output (0..4) each iteration, and you want to transform the
> sequence of pseudoentropy from that base-5 stream into an unbiased
> binary pseudoentropy stream with a 1-to-1 mapping from the base-5 stream
> to the base-2 stream.
> That's fairly easy. You fill a pseudoentropy register by repeatedly
> multiplying by 5 and adding the generator output.
> Then you can take binary output by taking the low bit of the
> pseudoentropy register and shifting right to divide by 2 (taking base-2
> digits from the integer).
> Whenever the pseudoentropy register gets to be small enough to hold
> another base-5 digit, you multiply it by 5 and add the output of the
> generator (essentially you'd be 'replacing' the base-5 digit you most
> recently took, had you been taking digits in base-5 rather than base-2).
Don't get it.
If the output of the generator is random then its binary notation is random too.
Why don't you use this directly, if you need a binary stream?
More information about the cryptography