Re: Imperfect random permutation of 2^k elements

From: Tim Smith (reply_in_group_at_mouse-potato.com)
Date: 04/11/04 

Date: Sun, 11 Apr 2004 00:58:45 GMT

In article <fcZdc.20640$tu5.3633@newssvr27.news.prodigy.com>, Bryan Olson
wrote:
> Benjamin Goldberg posted a shuffling algorithm that uses random bit
> sequences even more directly. See "Anti-sorting" sci.crypt, 2002-05-12
> currently available at:
>
> http://www.google.com/groups?selm=3CDE55AF.708814A1%40earthlink.net
>
> Goldberg's original post didn't claim it to be "perfect" in the same sense
> as algorithm P, but I thought it was interesting enough to examine, and I
> found that it does in fact generate all permutations with equal
> probability.
>
> http://www.google.com/groups?selm=3CDE8C65.4010400%40nowhere.org

I haven't analyzed the psuedocode in the first referenced post above, but
the C code given doesn't generate all permutations with equal probability.
It generates a subset of the permutations. Within that subset, all the
permutations seem to equally probable. For example, for 4 items, it only
generates:

    0 1 2 3
    0 2 1 3
    1 0 2 3
    1 2 0 3
    2 0 1 3
    2 1 0 3

I notice from later discussions in the thread that the C code has some
optimizations, so perhaps those optimizations broke something? 

-- 
--Tim Smith

Relevant Pages

  • Quantum Gravity Via Expansion-Contraction 35.1: Permutations, Combinations, etc.
    ... Aside from an idiotic comment by one of the loonie graffiti artists in ... celebration of the November Election idiocy with MoveOn.Org types), ... combinations in elementary and intermediate probability and ... while the number of permutations corresponding to these is: ...
    (sci.physics)
  • Quantum Gravity 320.4: "Exponential-Permutation-Combination Information"
    ... For more on how critical permutations and combinations are in physics ... The binomial probability distribution, b. ... The Fourier Transform, ...
    (sci.physics)
  • Re: Non-Scalar Cryptography - The Emporor is stark naked.
    ... Analysing the key probability as you have done will not affect the ... uncertainty of the ciphertext => the ciphertext still has equal ... the scrambling key is an absurdly small 16 bits; ... number of permutations reasonably quickly. ...
    (sci.crypt)
  • Re: Securing ARC4
    ... Is this applied before the normal RC4 ... Crypto primitives are hard to evaluate. ... permutations are more probable than others under your procedure. ... half the permutations have probability 4/27 and half ...
    (sci.crypt)
  • Re: Imperfect random permutation of 2^k elements
    ... >> Benjamin Goldberg posted a shuffling algorithm that uses random bit ... > the C code given doesn't generate all permutations with equal probability. ... bounds and exclusive upper bounds. ...
    (sci.crypt)