0
$\begingroup$

Let me ask whether my instant simple algorithm has serious flaws ,for cryptography use, or not. Which is supposed to randomly change the order on a given sequence S[1..n] of the length n. Assume I have a good random number generator random() which returns a random integer in the range [1..n].

while true   for i in 1..n     r=random()     swap S[i] and S[r] 

If it does not have serious flaws , when can I finish the while loop? Is there any well known algorithm which also easy to write a computer program?

Thank you in advance.

  • 7
    See [Fisher-Yates shuffle](https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle) and [this previous question](http://math.stackexchange.com/q/109126/856). Also, you probably shouldn't write cryptography routines unless you really know what you're doing.2012-03-04
  • 1
    Note that with the Fisher-Yates shuffle, the outer "while" loop is unnecessary. Simply going through the "for" loop a single time will do a perfect job (assuming that your random number generator is cryptographically secure and you don't make any mistakes).2012-03-04
  • 0
    @TannerL.Swett: Your comment is not very clear. The "for" loop must be like in the Fisher-Yates shuffle (with random generating a number in a varying range, for instance from $1$ to $i$ if you want to use the swap of the example given here); using random with a fixed range as the question seems to imply just won't do. Also if $n$ is quite large and you want all permutations to be possible ("a prefect job"), then you are almost asking the impossible for the state space of a pseudo-random number generator (but that is independent of the shuffling algorithm).2012-03-04
  • 1
    @Marc You're right; let me try to be more clear. @seven's algorithm tries to be more effective by shuffling multiple times; that's what the line "`while true`" is for. Sure enough, if a shuffling algorithm produces a non-uniform distribution, then repeating it is likely to produce a more uniform result. The Fisher-Yates shuffle, however, *is* uniform, so there's no reason to apply the FY shuffle multiple times, as long as your PRNG is itself secure.2012-03-05

1 Answers 1

4

The algorithm you suggest will not give you uniform distribution, so I guess it's not really what you want. A simple reason is that there are $n^n$ possible and equally probable runs of the algorithm (you choose a random number in $[1..n]$ and you do it $n$ times), while there are $n!$ different permutations. Since $n! \not | \ \ n^n$, it is certain that some permutations will get a larger chance of being chosen (though I don't have a clue which ones these are).

The links provided by Rahul Narain will point you to the right sources.

  • 0
    Thank you very much.I wonder whether my algorithm is not effective or my algorithm has flaws for cryptography.Won't repeating my algorithm equivalent to one round of the linked algorithm forever?2012-03-05