Re: Random number sequences

On Mon, 19 Jan 2009 15:08:23 -0800 (PST), Bill Bowden
<wrongaddress@xxxxxxx> wrote:

Question on probabilities:

I have an 8 bit random number generator that produces a maximum
length of 255 or 2^n-1. The output is xored with another 8 bits which
is incremented every 256 counts for a total length of 65536, but not
sure about that.
Technically a RNG that repeats after a number of outputs is a
Pseudo-RNG (PRNG) The difference may or may not be inportant.


The final output is divided by 10
Ten is not a good choice. If there are 256 outputs then you are
better off picking a factor of 256, like 16 or 32 to ensure even
distribution of the output. If you divide 256 by ten then you will
get a shortfall in the number of '25's compared with the number of
'00's to '24's. An alternative is to throw away all results from the
PRNG that exceed 249.

to produce numbers in the range of 0
to 24 which are used to reverse the positions of 25 numbers stored in
a data array (0 -24). There are always 25 unique numbers in 25
locations and the positions of 2 numbers are reversed according to two
random numbers. In other words, if two random numbers are say 7 and
12, the data at addresses 7 and 12 are reversed so the numbers are
continously scrambled always maintaining the unique original 25.
I suggest that you have a look at the structure of the RC4 stream
cypher (http://en.wikipedia.org/wiki/RC4) which uses a similar method.
In RC4 only one index is random, the other index increments steadily
through the array, thus ensuring that every position gets swapped at
least once on every full pass through the array.

i <- 0
repeat
j <- random
swap(array[i], array[j])
i <- (i + 1) mod array.size
until done


It seems the probabilities of arranging 25 numbers in various
orders is 25*24*23*22... etc for a total of around 1.5E25 or maybe
1.5 trillion squared, but I'm not sure I can get that much using a 16
bit random generator.
In theory there are indeed 25! possible permutations. In practice, if
you are using a PRNG then the fact that the PRNG repeat length is
shorter than 25! may render some of those permutations inaccessible.
The number of allowed permutations will still be very large, but
possibly short of the maximum.

One idea is to use a True-RNG (TRNG) in hardware, either directly or
to reseed a PRNG at reasonably frequent intervals. It is a standard
cryptographic technique to use a PRNG like this to "stretch" the
entropy from the TRNG as a TRNG is likely to be slow while a PRNG can
be fast. In many unix systems the TRNG is dev/random (which can
block) while dev/urandom (which does not block) is the TRNG -> PRNG
combination.


It seems the longer the process is allowed to run before displaying
the result increases the random possibilities, but the math escapes
me.
Probably, but if there is a bad interaction with the repeat length of
the PRNG then this might not be the case. According to Knuth, there
is no point in more than 25 RC4-style swaps for a 25 member array.

rossum


Anybody have a solution ?

-Bill

.

Relevant Pages

  • Re: True random number generator
    ... ring oscillators and use them as data or clock sources to feed ... Most other PRNG have N states. ... A simple example is the common linear congruence generator, which is the most used of all, many of the generators of George Marsaglia, and most if not all cryptographically secure random number generators. ... Many can be implemented with periods so long the universe will end before they repeat. ...
    (sci.electronics.design)
  • Re: Question About Cryptographically Hashing a Hash (SHA-512), Then Hashing That Hash, Etc.
    ... random number generator is initialized, ... because the "cycle" is all of the ... Aren't you confusing PRNG and TRNG here? ...
    (sci.crypt)
  • Re: distinguish TRNG from PRNG
    ... Are you talking about a TRNG, a PRNG, or a combination? ... The problem with restricting the bit rate to the randomness of the TRNG is ... >> radio interference. ...
    (sci.crypt)
  • Re: Random number sequences
    ... Pseudo-RNG (PRNG) The difference may or may not be inportant. ... In RC4 only one index is random, the other index increments steadily ... you are using a PRNG then the fact that the PRNG repeat length is ... entropy from the TRNG as a TRNG is likely to be slow while a PRNG can ...
    (sci.math)
  • Re: distinguish TRNG from PRNG
    ... This is a reply to multiple posts by multiple ... sampling a long time and correcting for the bias. ... TRNG idea out the window. ... A PRNG has a very known bias that is easily ...
    (sci.crypt)