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.

  • 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