Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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. –  Rahul Mar 4 '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 4 '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 4 '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 5 '12 at 1:40

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
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 5 '12 at 4:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.