0

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.

seven_swodniw
  • 837
  • 7
    See Fisher-Yates shuffle and this previous question. Also, you probably shouldn't write cryptography routines unless you really know what you're doing. –  Mar 04 '12 at 15:44
  • 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). – Tanner Swett Mar 04 '12 at 15:58
  • @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). – Marc van Leeuwen Mar 04 '12 at 17:00
  • 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. – Tanner Swett Mar 05 '12 at 01:40

1 Answers1

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.

Jakub Konieczny
  • 12,588
  • 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? – seven_swodniw Mar 05 '12 at 04:55