Re^6: How to generate different random numbers?

an attacker will surely notice...

Again, you are presuming a cryptographic application. No such presumption is warranted based on the root node.

Moreover, in terms of randomness, a random shuffle and just choosing a random number are vastly different.

What part of "indeed, a random shuffle of a known interval isn't the same thing as a set of random numbers... I never said they were the same thing." was unclear?

... the other is chosing a member from an infinite set with replacement. (emphasis mine)

A random number need not necessarily be chosen from an infinite set. Furthermore, an infinite number of randomly chosen numbers from a finite set is equivalent to a random selection from a continuous interval (infinite set). Therefore, a random shuffle (or multiple random shuffles, depending on the desired cardinality) can be transformed algorithmically into a random number suitable for cryptographic use.

Comment on Re^6: How to generate different random numbers?

Replies are listed 'Best First'.
Re^7: How to generate different random numbers? by thor (Priest) on Sep 08, 2004 at 12:02 UTC
Any time discussions turn to randomness and such, someone will use that discussion for security related purposes at some later date. That having been said, I feel that it's my duty as an upstanding netizen to bring to light the implications of certain things. On we go... Therefore, a random shuffle (or multiple random shuffles, depending on the desired cardinality) can be transformed algorithmically into a random number Unless you enumerate all of the permutations of the set, I don't know how this could possibly work. Even if you are, you're reducing the size of your output number drastically. There are n! ways to permute a set of n items. There are nn ways to choose n items from a set of n with replacement. The limit as n tends to zero of n!/nn is zero. What this means is that compared with the cardinality of just choosing n random numbers from 1 to n, generating a random number with from a random shuffle gets progressively worse for larger n. This would imply (well, to me anyways) that if you're looking for a random number, better to do it directly than to first shuffle and then transform that shuffle into one. A random number need not necessarily be chosen from an infinite set Point conceded. I mis-spoke. thor `Feel the white light, the light within Be your own disciple, fan the sparks of will For all of us waiting, your kingdom will come`	[reply]
Re^8: How to generate different random numbers? by Pragma (Scribe) on Sep 08, 2004 at 18:16 UTC
Unless you enumerate all of the permutations of the set, I don't know how this could possibly work. That's exactly what I'm doing; there is no need to limit yourself to individually selected numbers. If you treat each shuffled *set* as a random selection from the set of all possible shuffles, then you have a perfectly good random number, equivalent to a randomly selected integer from 1 to N!. If you do M shuffles, you can select random numbers from a set of size N! ^ M. It doesn't take a very large N and/or M to reach the cardinality needed from cryptographic applications.	[reply]
Re^9: How to generate different random numbers? by thor (Priest) on Sep 08, 2004 at 22:01 UTC
This works in theory. I think that it would become pretty unwieldy in practice though. Given a permutation of a set (let's say {5 1 3 2 4}), which permutation is that of {1 2 3 4 5}? The fourteenth or the forty-second? Wouldn't you have to pre-compute and store all of the permutations for this to work? thor `Feel the white light, the light within Be your own disciple, fan the sparks of will For all of us waiting, your kingdom will come`	[reply]
Re^10: How to generate different random numbers? by Pragma (Scribe) on Sep 08, 2004 at 22:14 UTC