Random Number Generation -----> Hardware or Software? - Page 4

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Re: Random Number Generation -----> Hardware or Software?
says...
Quoted text here. Click to load it

Don't forget the Polonium rinse.

--
  Keith

Re: Random Number Generation -----> Hardware or Software?
Quoted text here. Click to load it

As asked before, what about sqrt(two), pi, e ...?  Devil of a question.

--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
We've slightly trimmed the long signature. Click to see the full one.
Re: Random Number Generation -----> Hardware or Software?
Quoted text here. Click to load it

Not really in the same league IMHO:

Even though all these numbers seem to consists of effectively
unpredictable digits, strange things do happen, like the totally
unexpected discovery of a formula that allows you to calculate an
arbitrary hex digit in pi.

Terje
--
"almost all programming can be viewed as an exercise in caching"

Re: Random Number Generation -----> Hardware or Software?
Quoted text here. Click to load it

"Generating random numbers is too important to be left to chance".

(Knuth?)
...
I found a ref: http://www.c2i.ntu.edu.sg/resources/aipages/aiquotes.html

The generation of random numbers is too important to be left to chance.
-- R.R. Coveyou

Terje

--
"almost all programming can be viewed as an exercise in caching"

Re: Random Number Generation -----> Hardware or Software?
Quoted text here. Click to load it

Well, for a usable bit rate, yeah.  Otherwise a beta particle
detector, a little Americium, and an interval timer would do.

Fortunately, generating random numbers is rarely necessary.
Good-quality pRNG does for every application I know of,
including generating keys and nonce's for crypto apps.
--
Dennis M. O'Connor     snipped-for-privacy@primenet.com



Re: Random Number Generation -----> Hardware or Software?

Quoted text here. Click to load it
However if you do need random numbers without the pseudo bit then an Intel
Motherboard does the job.
http://www.lightstraw.co.uk/gpo/posb/ernie4.html
The UK Government Actuary's Department does statistical analysis on all the
numbers generated to verify that there is no discernable pattern.

Peter



Re: Random Number Generation -----> Hardware or Software?
On Sat, 5 Mar 2005 08:37:54 -0000 in comp.arch, "Peter"

Quoted text here. Click to load it


It uses a Logica motherboard with an Intel (810/815/830/845G?) chipset
including an 82802 FirmWare Hub whose RNG generates an octet in less
than 4.5ms (~0.5ms/bit?) Okay if you only need 11 digits/week for the
lottery, but at that rate, it would take 4 days to fill a CD. For
security uses, you'd want to collect the bytes on a timer and keep
them around for when you need a bunch of them quickly.

--
Thanks. Take care, Brian Inglis     Calgary, Alberta, Canada

snipped-for-privacy@CSi.com     (Brian[dot]InglisSystematicSW[dot]ab[dot]ca)
We've slightly trimmed the long signature. Click to see the full one.
Re: Random Number Generation --> Hardware or Software?



Peter wrote:

Quoted text here. Click to load it

Only certain no-longer produced Intel Motherboards. (Only those based
on the Pentium III or Pentium III Xeon processor with the 810/815/
820/845/850 Chipset AND the optional Intel 82802 Firmware Hub.)

See [ ftp://download.intel.com/design/chipsets/datashts/29065804.pdf ].
(See section 4.10 on page 28)

Quoted text here. Click to load it

ERNIE 4 isn't an Intel Motherboard. It's a specialized device that
uses an Intel 82802.

--
Guy Macon <http://www.guymacon.com/


Re: Random Number Generation --> Hardware or Software?

"Guy Macon" <http://www.guymacon.com/ wrote in message
Quoted text here. Click to load it

If you need only a modest number of truely random bits and don't want to buy
any hardware, but have network access, there is always John Walker's hotbits
for a free and readily available source.

http://www.fourmilab.ch/hotbits /

--
 - Stephen Fuld
   e-mail address disguised to prevent spam



Re: Random Number Generation --> Hardware or Software?


Quoted text here. Click to load it

No.

The set of prime numbers (there is only one) fails the "no amount
of knowledge will allow prediction of the next number" test.

The sets of random numbers (there are infinitely many) all pass
the "no amount of knowledge will allow prediction of the next
number" test.

The set of prime numbers is a member of the sets of random numbers,
but you cannot know that a particular set of random numbers is the
set of prime numbers without comparing them both to infinity. You can,
of course, know that a particular set of random numbers is not the
set of prime numbers; finding a single non-prime in the set proves that.

I believe that the set of all sets of random numbers is equal to the set
of all sets of numbers.

Nick Maclaren made the following claim, and when asked for evidence
supporting it, responded with insults rather than a rational argument.
(I predict that he will reply to this post with further insults - this
seems to be a pattern he follows whenever proven wrong).

Nick Maclaren wrote:

 "There is a universal test that will distinguish all pseudo-random
 generators from true ones.  Actually, there are many, and several
 have been known (to statisticians) since the 1920s, but there were a
 couple of 1980 (?) CS papers that described these as new :-)  Let's
 agree on that one."

This cannot possibly be true, because the set of numbers that are
outputs of pseudo-random number generators is a subset of the set
of numbers that are outputs of true-random number generators.

The exact same set of numbers may be output of a pseudo-random
number generator or the output of a true-random number generator
 - so how can Mr. Maclaren or his fictional statistics instructor
possibly distinguish between them?

There is no such paper.  Mr. Maclaren is invited to prove that one
exists by the simple act of citing one.  Further verbal abuse as a
substitute for reasoned discourse will be taken as Mr. Maclaren
admitting that he is grossly in error.

--
Guy Macon <http://www.guymacon.com/



Re: Random Number Generation --> Hardware or Software?
Quoted text here. Click to load it

Until and unless you post a specification of what you mean by a set
of random numbers, that is a meaningless statement.  It is not true
for the values of random variates (with probability one).

Quoted text here. Click to load it

No, you were offensive, and I pointed out that is is a standard, known
result in statistics.  If I recall, it is due to Kolmogorov.  Why don't
you look it up?

Quoted text here. Click to load it

Well, let's try a computer science approach :-)

Enumerate all pseudo-random number generators, with the meaning that
they are input-free Turing machines that generate a semi-infinite
output stream (of bits).

At each step N, generate the next bit from the first N pseudo-random
number generators.  Reject any that don't match, and don't use them
in the next step (but count them in the N).  Return 1 if there are
any not rejected, and 0 otherwise.

The test determines that a generator is pseudo-random if it ends in
a semi-infinite stream of ones.  Otherwise it is not.  This will get
answer right with probability one.

OK?


Regards,
Nick Maclaren.

Re: Random Number Generation --> Hardware or Software?

Quoted text here. Click to load it

Until and unless you post a specification of what you mean by a set
of random numbers, that is a meaningless statement.  It is not true
for the values of random variates (with probability one).

Quoted text here. Click to load it

No, you were offensive, and I pointed out that is is a standard, known
result in statistics.  If I recall, it is due to Kolmogorov.  Why don't
you look it up?

Quoted text here. Click to load it

Well, let's try a computer science approach :-)

Enumerate all pseudo-random number generators, with the meaning that
they are input-free Turing machines that generate a semi-infinite
output stream (of bits).

At each step N, generate the next bit from the first N pseudo-random
number generators.  Reject any that don't match, and don't use them
in the next step (but count them in the N).  Return 1 if there are
any not rejected, and 0 otherwise.

The test determines that a generator is pseudo-random if it ends in
a semi-infinite stream of ones.  Otherwise it is not.  This will get
answer right with probability one.

OK?


Regards,
Nick Maclaren.

Re: Random Number Generation --> Hardware or Software?

I am sorry to the people who have seen this three times - I failed to
notice that the newsgroups has been subtly edited.


Guy Macon  <http://www.guymacon.com wrote:
Quoted text here. Click to load it

Until and unless you post a specification of what you mean by a set
of random numbers, that is a meaningless statement.  It is not true
for the values of random variates (with probability one).

Quoted text here. Click to load it

No, you were offensive, and I pointed out that is is a standard, known
result in statistics.  If I recall, it is due to Kolmogorov.  Why don't
you look it up?

Quoted text here. Click to load it

Well, let's try a computer science approach :-)

Enumerate all pseudo-random number generators, with the meaning that
they are input-free Turing machines that generate a semi-infinite
output stream (of bits).

At each step N, generate the next bit from the first N pseudo-random
number generators.  Reject any that don't match, and don't use them
in the next step (but count them in the N).  Return 1 if there are
any not rejected, and 0 otherwise.

The test determines that a generator is pseudo-random if it ends in
a semi-infinite stream of ones.  Otherwise it is not.  This will get
answer right with probability one.

OK?


Regards,
Nick Maclaren.

Re: Random Number Generation --> Hardware or Software?



Nick Maclaren wrote:

Quoted text here. Click to load it

No.  It won't.

One on the characteristics of a true random number generator is
that any output stream is possible; if some output streams are
not possible then the generator is not a true random generator.

Among these possible output streams are output streams that are
identical to the output stream of any pseudo-random number
generator.  So if your test says "It's a PRNG" it really means
"It's either a PRNG or a True RNG that, by chance, just happened
to output the exact same stream that a PRNG would have generated."

Therefore, your "right with probability one" distinguisher cannot
exist.   The best you can do is a probability that approaches one.

I am well aware of Kolmogorov-Smirnov test and the Kolmogorov-
Chaiten definition.  One doesn't design hardware RNGs without
learning the basics.

The Kolmogorov-Chaiten definition of a random sequence is a sequence
that has the characteristic that the shortest computer program which
can generate it is as long as the sequence itself.  This is also known
as the compressability test.  This is easily disproven by counterexample;
take N bits the output of a hardware-based RNG and try to compress them
with PKZIP in self-extracting .exe mode.  In most cases the resulting
file will be larger - discard that result and try again.  Eventually,
by pure chance, the hardware-based RNG will output a sequence of N bits
that *can* be compressed into a smaller self-extracting .exe file.
That file is a computer program which generates the random sequence
and is shorter than the sequence itself.  If you have a very, very long
time to search and a very, very fast computer, eventually, by pure chance,
the hardware-based RNG will output a sequence of N bits that are all zeros
and which can be generated by a very simple computer program.

The Kolmogorov-Smirnov test is a statistical test that approaches
"right with probability one" as the output streams it tests approach
infinity. You can never reach "right with probability one."  
An additional difficulty is that The Kolmogorov complexity of
sequence is not computable, even with infinite resources.

--
Guy Macon <http://www.guymacon.com/


Re: Random Number Generation -----> Hardware or Software?
On Intel's motherboard/chipset RNG:

http://home.comcast.net/~andrex/hardware-RNG /

--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
We've slightly trimmed the long signature. Click to see the full one.
Re: Random Number Generation -----> Hardware or Software?
Quoted text here. Click to load it

Any good random number generators that I know of rely on the system clock -
and specifically,  are based on the number of milliseconds that have elapsed
as a "seed" value.

The hardware platform will then use this seed value as an offset value into
a hard-coded lookup table in memory.  Two numbers generated in a row will
have similar offsets into the table but their resulting values will depend
on the corresponding table values at those offsets.

Basically, any crude hardware device that is able to oscilate can be used as
an offset for a random number generator table, such as a simple capacitor
that is able to charge and discharge.  Of course, the more "randomness" that
is desired, the bigger the lookup table needs to be.

A crappy random number generator could also be created to use only a lookup
table and simply increase the offset into the table by 1 each time.  This is
not true randomness by any stretch of the imagination.

--
MT



Re: Random Number Generation -----> Hardware or Software?
Quoted text here. Click to load it

Agreed, the randomness is supplied by the timing of the human hitting the
keyboard and asking for a number.

The reality is a bit different however.  The result will have a constant
bias.  Interestingly, JvonN's method does not remove the bias.

JvonN's method for correcting an unfair coin:

 If 1's and 0's have a different frequency then the data can be made
 unbiased by considering only strings of 01 and 10 and removing all
 11..1 and 00...0 strings.

I spent a few years on the electronic generation of random numbers.  It
can't be done, there is always a bias, but that in itself is part of the
randomness of the results.  A sort of 1/f noise.

Oh, yes.  The lack of 1/f noise -- the longer the timeframe the wilder
the swings -- is one dead give-away to a prng.  A prng has a hard limit
on the length of a winning streak.

--
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
We've slightly trimmed the long signature. Click to see the full one.
Re: Random Number Generation -----> Hardware or Software?
Quoted text here. Click to load it

Software.  The most common (and one of the simplest) is the linear
congruential type, which implements:

   R(n+1) = (R(n) * K1 + K2) modulo K3

and the seeding process sets R(n).  The magic is in picking the
various K's, which can result in fairly good or very bad pseudo
random sequences.  Knuth has a thorough discussion.  A more complex
system is the Mersenne Twister.  You can google for that, or find
an implementation (used for testing) within my hashlib package at:

  <http://cbfalconer.home.att.net/download/hashlib.zip

--
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on
We've slightly trimmed the long signature. Click to see the full one.
Re: Random Number Generation -----> Hardware or Software?
Quoted text here. Click to load it



And unfortunately almost all programming language runtime systems
have historically used generators with at best 32-bit math (some
are even limited to 16 bits!) resulting in *terrible* "random"
number output, certainly not anything useful for security or any
statistical process.  In fact the inappropriate use of such built-in
"randomness" sources has frequently been used to defeat real-world
security systems based on them.

Quoted text here. Click to load it

One of the best places to learn about the use of serious PRNGs these
days is from (of all places) online casino companies.  Most have pages
dedicated to explaing why their systems are fair/secure and some of
these go into a surprising amount of detail about PRNGs.  The Mersenne
Twister seems to be a favorite there as well.

A similar application is in massively multi-player online games, where
PRNGs are used to determine issues such as which player gets a treasure
item, etc.  One of these is World of Warcraft by Blizzard Entertainment,
who recently addressed questions about whether players were cheating at
aspects of the random processes:

http://forums.worldofwarcraft.com/thread.aspx?fn=wow-general&t18%06053&p=1&tmp=1#post1806053

G.

Re: Random Number Generation -----> Hardware or Software?
snipped-for-privacy@allegro.com (Gavin Scott) writes:

Quoted text here. Click to load it

Ada has some requirements on the built-in (pseudo) random number
generators.  See:

http://www.adaic.org/standards/95aarm/html/AA-G-2-5.html

I don't really understand this stuff.  Does it result in "terrible",
as you say, output?

- Bob

Site Timeline