Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re^5: How to generate different random numbers?

by thor (Priest)
on Sep 08, 2004 at 03:19 UTC ( [id://389269] : note . print w/replies, xml ) Need Help??


in reply to Re^4: How to generate different random numbers?
in thread How to generate distinct random numbers?

A random shuffle is really a random selection from a uniform distribution of the set of all possible permutations on that range of numbers (or N!).
This assumes that you're chosing one member from the interval. However, even this has a gotcha or two. If you do this on a large scale, an attacker will surely notice that all of your "random" numbers come from the same interval and exploit this fact.

Moreover, in terms of randomness, a random shuffle and just choosing a random number are vastly different. One is chosing a member from an finite set without replacement, the other is chosing a member from an infinite set with replacement. That is to say that in the true random case, you are just as likely to pick the number that you just picked as you are any other number. In the random shuffle situation, you are guaranteed that this is not the case. An attacker can exploit this, too. For instance, let's say that the interval was [1,4]. As the attacker, you have this knowledge. Furthermore, you've observed, the following numbers go by: 2, 4, 1. What's the next number in the sequence?

And who said the numbers had to be used for cryptographic purposes?
Is there any other use? ;)

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

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

Replies are listed 'Best First'.
Re^6: How to generate different random numbers?
by Aristotle (Chancellor) on Sep 08, 2004 at 20:38 UTC

    the other is chosing a member from an infinite set with replacement.

    Any number expressible inside a computer is one out of a finite set.

    Using a computer to pick a random number "without" an interval simply means picking some x where 0 <= x <= 2n-1.

    Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.
    John von Neumann

    Makeshifts last the longest.

Re^6: How to generate different random numbers?
by Pragma (Scribe) on Sep 08, 2004 at 04:38 UTC
    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.

      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 n**n ways to choose n items from a set of n with replacement. The limit as n tends to zero of n!/n**n 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

        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.