Board index » delphi » How random is the random number generator?

How random is the random number generator?

Is the random number generator truly random?

Certainly tests i have done appear OK , but do/
would the results mirror 'true life' randomness?

Ken

 

Re:How random is the random number generator?


Quote
kc wrote:

> Is the random number generator truly random?

> Certainly tests i have done appear OK , but do/
> would the results mirror 'true life' randomness?

> Ken

NO, any random generator of this kind can never be
truly random, this follows from the fact that once
you know the algorithm used you can always tell
the next number generated. (The definition of a
random number sequence is that you can not from
history tell the next number to come).

The criteria for a good (pseudo-)random generator is
that you cannot distinguish the number sequence it
generates from a truly random sequence by analyzing
the statistics on the generated numbers.

This being said, I have run a number of tests on the
(pseudo-)random generator and found it to be very
good for most purposes. (See "Knuth" for suggestions
on how to test random generators). Still, a random
generator should never be applied to any application
without verifying that the statistics hold for that
particular use.

regards Sven

Re:How random is the random number generator?


kc <ke...@zetnet.co.uk> wrote in article <572qbg...@irk.zetnet.co.uk>...

Quote
> Is the random number generator truly random?

No, it is not. If you want "truly random" numbers, you need to take some
physical measurement of something reasonably random, then post-process it
to distribute the randomness fairly uniformly. One good technique for a few
good random numbers is to have a "pool" of numbers that you "stir" with
some measurement. One way is to use mouse location and timing from a
MouseMove event to update a running CRC-32 that is also updated with the
system time every time you pull a random number out of the "pool" (by using
the CRC-32 at that time for a random long integer). This gets you random
numbers that are not only uniformly distributed, but quite unpredictable.
Of course, if no mouse "squeaks" are captured, the randomness is not that
great, but still better than the built-in random number generator because
of variations in timing that are very unlikely to be the same from one run
to another, or from one system to another.

Re:How random is the random number generator?


"Michael Paul Johnson" <m...@exabyte.com> wrote:

Quote
>kc <ke...@zetnet.co.uk> wrote in article <572qbg...@irk.zetnet.co.uk>...
>> Is the random number generator truly random?

I design psychology experiments that run on computers. One technique
that I have used to assure randomness is to sample random numbers in a
loop and only pick the one I am going to use when the user makes a
keypress or mouse click. The sampling is done so often, compared to
the interval between human responses, that it would be impossible to
predict which number will be selected. Of course, this will only work
if you can key in on the user's responses.

Joe D.
joed...@i-2000.com

Re:How random is the random number generator?


Quote
In article <572qbg...@irk.zetnet.co.uk>, ke...@zetnet.co.uk wrote:
>Is the random number generator truly random?

>Certainly tests i have done appear OK , but do/
>would the results mirror 'true life' randomness?

The random number generator is not random at all.  

However, for some uses, it may be as good as a something that is random.

Brian

Re:How random is the random number generator?


Quote
Sven Pran wrote:

> kc wrote:

> > Is the random number generator truly random?

> > Certainly tests i have done appear OK , but do/
> > would the results mirror 'true life' randomness?

> > Ken

> NO, any random generator of this kind can never be
> truly random, this follows from the fact that once
> you know the algorithm used you can always tell
> the next number generated. (The definition of a
> random number sequence is that you can not from
> history tell the next number to come).

> regards Sven

Well, as I have pointed out in my previous post (Not mailed yet when I
read yours.) it IS fully possible to create a TRULY random RNG, *IF* you
are willing to get down and dirty in the hardware side.  By creating a
source of truly random seed values and running your RNG against these
seed values, you will get the randomness you seek from ANY reasonably
random RNG.  

No doubt you're going to ask just where you get these random seed
values.  The same place NASA, NSA, CIA and other government crypto
agencies do!!!  You run a receiver tuned to the random atmospheric
noise.  This has the features that YOUR area's RAN is different than
that experienced by people just a few dozens of miles away; it is NOT
predictable; and it is easily captureable with just a few dollars worth
of FM receiver (The less quality the receiver, the better as more noise
gets through the filters!), ADC converter and ADC support software.

HTH

Derek

Re:How random is the random number generator?


Quote
Michael Paul Johnson wrote:

> kc <ke...@zetnet.co.uk> wrote in article <572qbg...@irk.zetnet.co.uk>...
> > Is the random number generator truly random?

> No, it is not. If you want "truly random" numbers, you need to take some
> physical measurement of something reasonably random, then post-process it
> to distribute the randomness fairly uniformly. One good technique for a few
> good random numbers is to have a "pool" of numbers that you "stir" with
> some measurement. One way is to use mouse location and timing from a
> MouseMove event to update a running CRC-32 that is also updated with the
> system time every time you pull a random number out of the "pool" (by using
> the CRC-32 at that time for a random long integer). This gets you random
> numbers that are not only uniformly distributed, but quite unpredictable.
> Of course, if no mouse "squeaks" are captured, the randomness is not that
> great, but still better than the built-in random number generator because
> of variations in timing that are very unlikely to be the same from one run
> to another, or from one system to another.

Michael,  I think you could get better randomness from this, even when
the mouse is *NOT* moving if you ran a separate RNG on the system timer
and combined *its* result with the current value that you're running
your CRC-32 on.  Or, even better, don't *always* use the other RNG
value, only if there is NOT a current Mouse event!!!  However, I'd have
to say that setting up a small antenna, hooking it up to a CHEAP FM
receiver kit, piping the output into an ADC and concatenating the bytes
into 256-bit groups would work best.  

Let's see, you wouldn't even have to set up an antenna since you can get
one of the mini-boombox FM radios for about $5-$10.  Then you'd just
siphon the signal off from just before it's routed to the speakers.  As
this is just like the technique used to generate the 'random atmospheric
noise' cryptographic key CD-ROMs used by the government, I think this
would qualify as a *TRULY* random source of values.  (Oh!  Yeah!  I
forgot to mention that you'd tune the sucker to a channel that had a lot
of atmospheric hiss and noise but not any easily discernable broadcast
signal.  These days, most stations repeat their playlist so often that
you might get repeat VERY quickly!)

What makes this so attractive is that anyone with just a minimum of
skill can hook the wire between the radio and an in-the-pc ADC/DAC card
and the whole thing can be done for under $50 USDollars!  Run those
digits through your CRC-32 RNG and you'll get randomness like you'd
never believe possible!!!

HTH

Derek

P.S.  The magazine, 'Electronics Now' or 'Circuit Cellar, INK' both have
tiny FM receiver kits that could be used instead of the mini-boombox I
suggested, as well as ADC/DAC cards.

Re:How random is the random number generator?


Quote
Derek A. Benner wrote:

> Sven Pran wrote:

. . . .
> > NO, any random generator of this kind can never be
> > truly random, this follows from the fact that once
> > you know the algorithm used you can always tell
> > the next number generated. (The definition of a
> > random number sequence is that you can not from
> > history tell the next number to come).

> > regards Sven

> Well, as I have pointed out in my previous post (Not mailed yet when I
> read yours.) it IS fully possible to create a TRULY random RNG, *IF* you
> are willing to get down and dirty in the hardware side.

Yes, this is indeed true, but I believe not very relevant to the
original
question?

Quote
>  By creating a
> source of truly random seed values and running your RNG against these
> seed values, you will get the randomness you seek from ANY reasonably
> random RNG.

This is NOT necessarily true, it takes a lot of continuous monitoring to
verify that the final digit sequence is really random. And for most work
it is not sufficient to assume that a RNG produces random sequences, you
should always be able to demonstrate that it does. In fact, proving that
a physical process results in true randomness (after signal processing)
is definitely no trivial task.

Quote

> No doubt you're going to ask just where you get these random seed
> values.  The same place NASA, NSA, CIA and other government crypto
> agencies do!!!  You run a receiver tuned to the random atmospheric
> noise.

How can you be sure that the signals you receive is random atmospheric
noise and nothing else?

Quote
>  This has the features that YOUR area's RAN is different than
> that experienced by people just a few dozens of miles away; it is NOT
> predictable; and it is easily captureable with just a few dollars worth
> of FM receiver (The less quality the receiver, the better as more noise
> gets through the filters!), ADC converter and ADC support software.

But will the cheap receiver be immune against non-random radio
transmitter
intereference? I don't believe it.

At my company long time ago we had some equipment producing key tapes
for the crypto units used by NATO  (and incidently also on the hot line
between Washington and Moscow). This derived the random sequences from
radioactive isotopes. I remember several hardware monitors connected,
one
of them was even designed to discard the process in the (unlikely) case
that too many zeroes or ones came in a row. Although such sequences are
indeed part of a truly random sequence you don't want them for this use.
(So what about the true randomness after we removed such sub-strings?).

Usually when you produce random numbers you want a sequence that can be
used for a particular purpose, and depending upon the purpose you must
be able to control the statistics, but you do not necessarily need true
random numbers. What you do need is the ability to show that the
sequence
statistics comply with the requirements of the application, and in
certain
cases the ability to reproduce the sequence under full control.

Bottom line is that I think we have derailed. Except for crypto use I
think
we can happily use the built-in RNG in TP and Dephi, but test it first
with
the actual  application to verify that it really is suitable.

Sorry for the length of this comment, but I hope I made a point.

regards Sven

Re:How random is the random number generator?


Quote
> kc wrote:

> > Is the random number generator truly random?

> > Ken

> NO, any random generator of this kind can never be
> truly random, this follows from the fact that once
> you know the algorithm used you can always tell
> the next number generated. (The definition of a
> random number sequence is that you can not from
> history tell the next number to come).

True, but if you base the selection of the rand number on the curent time,
you'll get a pseudo random number.  You may know the algorithm, but you
won't ever know the exact time the random function is called, so you won't
know what number is selected.
See Heisenberg's Random Number Generator ;)

Daniel Spiess
dspi...@frii.com

Re:How random is the random number generator?


In article <01bbe013$ea0028a0$b9f290cc@dspiess>, Daniel Spiess or Petra
Lowe <dspi...@frii.com> writes

Quote

>> kc wrote:

>> > Is the random number generator truly random?

>> > Ken

>> NO, any random generator of this kind can never be
>> truly random, this follows from the fact that once
>> you know the algorithm used you can always tell
>> the next number generated. (The definition of a
>> random number sequence is that you can not from
>> history tell the next number to come).

>True, but if you base the selection of the rand number on the curent time,
>you'll get a pseudo random number.  You may know the algorithm, but you
>won't ever know the exact time the random function is called, so you won't
>know what number is selected.
>See Heisenberg's Random Number Generator ;)

>Daniel Spiess

It is also true that sometimes it is important to know that the
IDENTICAL *random* number stream is delivered every time! As when a
series of replications are carried out on a simulation model with
changing parameters for each run.

Jim

Jim Barr        Machine Conversation
                http://www.wandana.demon.co.uk/
                Best is the enemy of good enough

                Leaves rustle,   blades turn,    water moves

Re:How random is the random number generator?


No one actually told the poor person to use the randomize()  to start the
random sequence which will start the pseudorandom generator with a time
based seed.
--
Brian C. Layman
Director of Software Development
SoftForms Development Corporation
http://www.softforms.com
BLay...@Softforms.com

Daniel Spiess or Petra Lowe <dspi...@frii.com> wrote in article
<01bbe013$ea0028a0$b9f290cc@dspiess>...

Quote

> > kc wrote:
> True, but if you base the selection of the rand number on the curent
time,
> you'll get a pseudo random number.  You may know the algorithm, but you
> won't ever know the exact time the random function is called, so you
won't
> know what number is selected.
> See Heisenberg's Random Number Generator ;)

> Daniel Spiess
> dspi...@frii.com

Re:How random is the random number generator?


In article <01bbe85e$3f701320$918794ce@FormSoft>, "Brian C. Layman"

Quote
 <BLay...@SoftForms.com> wrote:
>No one actually told the poor person to use the randomize()  to start the
>random sequence which will start the pseudorandom generator with a time
>based seed.
>Daniel Spiess or Petra Lowe <dspi...@frii.com> wrote in article
><01bbe013$ea0028a0$b9f290cc@dspiess>...

>> > kc wrote:
>> True, but if you base the selection of the rand number on the curent
>time,
>> you'll get a pseudo random number.  You may know the algorithm, but you
>> won't ever know the exact time the random function is called, so you
>won't
>> know what number is selected.
>> See Heisenberg's Random Number Generator ;)

Pascal's pseudo-random number generator is based on linear modular residues:
X(n+1) = ( a*X(n) + b )mod c

Knuth's Art of Computer Programming Volume 2, "Seminumerical
Algortithms" discusses this kind of random number generator and tests for
randomness of a sequence. Bruce Schneier's "Applied Cryptography", 2nd. ed.
discusses a few more generators and how secure (unpredictable) they are.

Jeffrey T. Donville
donvi...@direct.ca / donvi...@rmd.klohn.com
http://mypage.direct.ca/d/donville/

Other Threads