Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

By someone's suggestion, I am posting this question from math.stackexchange.com.

I want to find out a suitable function or algorithm, which can provide a random sequence like this…

Input: $3$
Output: $\{1,2,3\}$ or $\{1,3,2\}$ or $\{2,1,3\}$ or $\{2,3,1\}$ or $\{3,1,3\}$ or $\{3,2,1\}$

Same as if I will enter a number $N$, output will be a random permutation of the set $\{1,2,...N\}$.
How can a I write this type of algorithm? And can you help me understand the logic behind it?

share|improve this question
    
No closed form function can describe a truly random permutation by definition. But if $N = 2^k$, then block ciphers come a significant fraction of the way. –  Thomas Aug 29 '12 at 17:27
    
Please don't cross post. Nobody suggested you should. Someone suggested a migration, and even that was dubious. –  CodesInChaos Aug 29 '12 at 18:12
add comment

2 Answers 2

The classical way to generate a random permutation is the Fisher-Yates shuffle; it takes an underlying random number generator, and produces a random permutation. With just a bit of care, it can generate each permutation with equal probability (assuming the underlying random number generator outputs are independent and uniformly distributed).

The only downside is that the algorithm requires N to be small enough so that you hold the entire permutation in memory; that doesn't sound like that's a problem from you.

share|improve this answer
    
Sorry, But I don't want to use any buffer to store anything. –  Rahul Taneja Aug 29 '12 at 17:31
2  
@RahulTaneja: you said you wanted the output to be the random permutation. If you didn't want to use a buffer, how is the function or algorithm supposed to return you the permutation? –  poncho Aug 29 '12 at 17:32
add comment

If for some reason the solution given by @poncho does not please you (e.g. you want $N$ to be on the magnitude of a few billions but you do not have a few gigabytes of RAM), then there are other solutions, in which you get the permutation as an evaluable procedure (in other words, a block cipher).

A practical solution is the Thorp shuffle. It is approximate, but the approximation can be made as good as needed by adding more rounds (except that, as a Feistel-derivative, it implements only even permutations, so if the attacker knows the output for $N-2$ inputs he can compute the last two outputs with 100% certainty). There is also a "perfect" solution but it involves some floating-point operations which needs potentially unbounded accuracy, so in practice it is very expensive.

share|improve this answer
1  
Can't any even-permutations-only generating cipher be made "perfect" by a trivial postprocessing conditionally switching two outputs (with a 50% probability based on the key)? –  maaartinus Aug 31 '12 at 0:23
    
@maaartinus: I tend to think so, but it would deserve some careful analysis. –  Thomas Pornin Aug 31 '12 at 13:12
add comment

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.