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

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?
Quoted text here. Click to load it


There are readily available PRNGs that operating at one output per
nanosecond would take longer than the current age of the universe
to repeat.

Any frequency check you can actually perform on them within your
lifetime will not reveal the periodic cycle.

Eric

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

I should amend the above to: "Prng's pass randomness checks with
100% flying colors and that's why they fail.  They cheat on the test."

Yes, it is theoretically possible to create a prng with some arbitrarily
long repeat cycle.  And one can postulate that in some arbitrarily long
lived universe the pattern will repeat.

That is not the point.  The pattern is not random.  It is deterministic.
If the generating method is known then each number coming out is known
with 100% certainty.  The only thing random about such a generator is
the algorithm.  The seed at which it starts is irrelevant to the
discussion: the sequence is circular - any starting point on the
circle is equivalent to any other.

It is like reading a book (it is exactly like reading a book), though
one may not know the next word, there is only _one_ possibility.
There is _no_ uncertainty.  That the observer is ignorant does not
make the sequence random.

A prng is nothing more than a _counter_.  The old TMS1000 micro used
a prng for the program counter because it could be made with less silicon
than a 'real' counter.  Debug was a gas ...

A zener diode and a comparitor will produce a sequence that can not
be predicted.  It being a real implementation it will have bias but
in the limit it becomes impossible to tell bias from 1/f noise.  The
next generator built will have a different bias, etc. etc.

Good Lord.  Get thee to a palmist and have a seance with von Neumann
and Turing and ...  Far better minds than those here have declared
PRNG's to be mirage.

As the saying goes "The mind of God is unknowable", and I would
add "even to God".

--
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

It is even possible to generate a PRNG that does not repeat. It may stop
working due to memory limits at some point, but it does not need to repeat.
Like a algorithm that produces all digits of pi, it will be fully
deterministic, though.

Quoted text here. Click to load it

Or the thermal noise of a resistor. If you use an auto-zero amplifier, the
bias goes away, but the noise level depends on temperature. Add an
automatic gain control (which takes the noise amplitude only), and you get
rid of that influence, too.

--
Bernd Paysan
"If you want it done right, you have to do it yourself"
We've slightly trimmed the long signature. Click to see the full one.
Re: Random Number Generation --> Hardware or Software?



Bernd Paysan wrote:

Quoted text here. Click to load it

There is a far better method, one that I used when I designed a
hardware RNG.

Take any repeating but random event.  Thermal noise crossing zero,
radioactive decay events, key-presses, cosmic rays - any event that
repeats at somewhat random intervals.

Make a high resolution timer with a very stable high frequency
clock.  Use it to measure the time of each event.

Measure time between two consecutive events.  If the time is longer
than the last time between the last two consecutive events, output a
one.  If it is shorter, output a zero.  Don't output anything if it
is a tie.

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


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

Yes, that would work, but is very complex.  There are easier approaches
to removing bias.

A) Generate bits in pairs, ignore ones that are the same, and convert
(0,1) to 0 and (1,0) to 1.

B) Generate bits, in parallel generate alternating 0 and 1, and return
the exclusive or of the two.

I should require notice of the question of whether your method is
likely to be better at removing flaws other than bias - it may well
be - the ones that I describe remove only bias.  The second can be
extended to any fixed size group of bits, of course, in the obvious
way :-)


Regards,
Nick Maclaren.

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



Nicholas O. Lindan wrote:

Quoted text here. Click to load it

Exactly so.

I am guessing from some of your comments that you may be under the
false impression that I have claimed some sort of uncertainty or
some departure from determinism in a PRNG, but if you examine my
posts you will fail to find any example of me making such a claim.

I *do* claim that there exist PRNGs where the observer is ignorant
and cannot become non-ignorant by looking at the output. For example:

01234567890123456789012345678901234567890123456789...
(Take it out as far as you wish, including to infinity).

Is it the output of a PRNG?  You don't know for sure.  
Maybe it is a random pattern that just happens by chance
to be exactly the same pattern as the output of a simple
repeating 0-9 counter.  Unlikely, but possible.  If that
pattern wasn't possible, it wouldn't be a random pattern.
All you can do is look at the statistics and assign a
probability (in this case very high, in the case of a good
PRNG very close to 50/50) that it is the output of a PRNG.

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


  
  

  


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

This has nothing to do with randomness and everything to do with
security. Whetever some generator is random vs secure is entirely
different mater to it being secure.

--
    Sander

+++ Out of cheese error +++

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




Having a long period is "cheating"?  I'd think it would be a desirable
characteristic of a PRNG.

Quoted text here. Click to load it

Where did I say it was?  I only contradicted the idea that in practice,
all PRNGs "have to" fail multi-dimensional frequency checks.  If you
want to postulate running a test for an arbitrarily long time (perhaps
billions of years), I don't think that can be considered useful in terms
of proving or disproving the randomness of a generator.  I'm rather more
interested in tests that can be completed within a reasonably small
fraction of my own lifetime, even if they must in some cases produce
incorrect results.

Eric

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



Eric Smith wrote:

Quoted text here. Click to load it

Exactly so.  Alas, all True RNGs "have to" fail multi-dimensional
frequency checks; you just have to keep testing them over and
over until you get an output that fails the test.  It may take
a really huge number of tries but it will happen if you try often
enough.

In addition, even if you *do* have those billions of years, a rather
modest increase in the number of bits in the internal PRNG state will
make it so that you need quintillions of years to prove that an output
is from a PRNG, which means that you need quintillions of years to
try the same test and fail when testing the output from a true RNG.

The idea of a known method that can differentiate between True RNGs
and PRNGs with absolute certainty is a fantasy of the type often
cooked up by those who have had some exposure to theory but have
never created any actual systems.  If one is willing to be satisfied
with answers such as "this output has a 99.999999% chance of being
the output of a such-and-such PRNG", then the job can be done.
Alas, identifying something as being from a particular PRNG is a lot
easier than identifying something as being from any PRNG, including
ones not yet invented.  Identifying something as being from a true
RNG is even harder - so hard that many educated people doubt whether
a true RNG with 100% entropy exists.

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


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

Quoted text here. Click to load it


Diehard Battery of Tests of Randomness

stat.fsu.edu/pub/diehard/
www.cs.hku.hk/~diehard/
random.com.hr/products/random/manual/html/Diehard.html

And for a distillation of the Diehard Battery into 3 tests, see:

www.jstatsoft.org/v07/i03/tuftests.pdf

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

Sigh.  This is what comes of a poor understanding of the unrealistic
models so popularised by modern computer science courses.  I did some
work on this a while back - here is a VERY rough summary:

1) 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.

2) There is a universal pseudo-random generator that will pass all
tests as truly random.  This operates by simulating all tests (there
are only a countable number, after all) and choosing a sequence that
will "fail the failure test" for each.  A simple variant of Turing's
diagonalisation proof.

The key is that the proofs use different models of complexity.  In
both cases, they allow the favoured antagonist unlimited resources
compared to its opponent.  In the first case, a mere exponential
increase in complexity is needed; in the latter, it is rather more
evil.

There is very similar situation with designing for reliability and
security - or in breaking them - where the first question is "what
are we protecting against?"  It is a classic axiom of military
intelligence that you can overwhelm any system if you put enough
resources into doing so.

Quoted text here. Click to load it

And exactly why should a pseudo-random generator be restricted to a
bounded state space?  Why shouldn't it increase its workspace as time
goes on?  Sorry, you aren't being imaginative enough.

Quoted text here. Click to load it

Your first sentence is religion, not engineering.  They may be, but
we don't know.

Secondly, you CAN remove single-bit bias, or bias in any bounded
number of bits.  Again, good 1930s results.

Thirdly, if you think that a pseudo-random generator has no defects,
you haven't looked hard enough :-(


Regards,
Nick Maclaren.

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



Nick Maclaren wrote:

Quoted text here. Click to load it

Evidence, please.


Because the universe is finite, and thus the PRNG cannot increase
its workspace without bounds.  Sorry, you are being too imaginative.

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


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

No problem.  Enroll on a serious statistics course, and all will be
revealed.  I do not, of course, mean Remedial Statistics for the
Mathematically Impaired.

Quoted text here. Click to load it

You clearly haven't looked at the published universal tests.  All
of them need an unbounded state space.  Oh, sorry, I forgot that you
haven't been on the statistics course yet.


Regards,
Nick Maclaren.

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



Nick Maclaren wrote:
Quoted text here. Click to load it

Riiiight.  The best cryptography experts in the world say that a
cryptographically strong PRNG is indistinguishable from random
data, the best known software for identifying bias (DIEHARD)
cannot find bias in cryptographically strong PRNGs, yet I am
supposed to believe that this unnamed method is taught in
statistics courses.  Suuuure it is.

Look here for evidence that you are wrong:
http://www.google.com/search?q=prng+%22indistinguishable+from+random%22

Quoted text here. Click to load it

And this allows an unbounded state space to fit inside a bounded
universe - how?


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

Quoted text here. Click to load it

These the same crypto experts who bring us all these crackable
codes.  A prng is just one more code.  It is crackable just
like any other.  By _definition_.

Quoted text here. Click to load it

Philosophy, literature, art, religion ... stats hasn't caught
up yet.  In my mind PLA&R kick over rocks for stats to come and explain
at some later date.

Quoted text here. Click to load it

Funny.  None of them say prngs are really-truly random.  They say
you can get 'good enough'.

And I didn't know Google was a particularly good source for the truth:

http://www.bonsaikitten.com/bnw.html

And

http://www.timecube.com /

And if you liked the timecube:

http://www.geocities.com/loudster/ripping_gore/web_weirdness.htm

Quoted text here. Click to load it

And I can't believe I agree with Macon.  Aw, it's just a random event.

--
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?



Nicholas O. Lindan wrote:

Quoted text here. Click to load it

Of course it is.  However, the claim I responded to was *not*
a claim that all PRNGs are crackable, but rather a claim that
there exists a method, taught in statistics classes, that can
distinguish the output of a PRNG from a true random output.
*That* claim is false.  They can all be cracked, but there
does not at this time exist a method that can crack them all.

Quoted text here. Click to load it

Nor do I say such a silly thing.  I only say that you can't tell
whether the output is from a PRNG or is really-truly random.
See proof below.

Quoted text here. Click to load it

That's what I say as well.  In particular, you can get good enough that
the output cannot be distinguished from a true random output using any
known method running on any known hardware.

The proof is as follows:


[1]
A true random source can have any output pattern.  If any patterns are
impossible, it isn't a true random generator.  

[2]
"Any output pattern" includes the *exact same* patterns as are produced
by any and all PRNGs.

[3]
Therefore, one cannot look at an output pattern and tell for sure
whether it came from PRNG X or a true random number generator that
just happened to have that exact same output by random chance.

In addition to the absolute proof above, there are the following
difficulties for any realizable system:

[A]
All known methods running on all known hardware are limited to
examining only a finite amount of the output.  If the universe
is finite, all possible methods running on all possible hardware
will have the same limitation.    

[B]
A PRNG produces a deterministic pattern.  If it has a finite internal
state it must repeat, but even seeing it repeat a billion times does
not tell the person examining the output that it will repeat the
billion and first time.  You need to look at an infinite amount of
output to know for sure that it doesn't stop repeating at some point
above the highest number you looked at.

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



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

The boundedness of the universe is not a settled question.

Regards
Emil

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

True, and anyway it's kind of irrelevant, isn't it?  The set of positive
integers, for example, is an infinite set whether or not the universe is
  infinite.

Ed


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

In order to prove that reduction to absurdity is not a valid method
of proof, I have set a machine (down in the basement) to
discovering and displaying the largest prime.  It does this quite
simply, by displaying all numbers that are not the largest prime.
It is making steady progress.

For efficiency reasons it does its displaying in hex.  So far I can
confidently assert that the largest prime is not less or equal to:

0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

The result will eventually require confirmation, because the ECC
memory cannot correct multiple bit errors, in fact it cannot even
detect all 3 bit errors.  In case someone wants to do this in
parallel, rather than after I publish the end result, suitable C
code follows:

   i = 0; largestprime = 0;
   while (i >= largestprime) {
      if (i && prime(i)) largestprime = i;
      printf("0x%x\n", i);
      if (!++i) break;
   }

and there are plenty of published methods of evaluating prime(i).

Note: the C system must have a suitable value of INT_MAX, otherwise
the above code can exhibit undefined behaviour.

--
"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

I have a similar experiment running:

for (i=POS_INFINITY; !prime(i); i--);

As you can see, it's a more efficient algorithm since it starts at
positive infinity and decrements.  However, after running for a few
weeks, it's still initializing i.  If it ever finishes, I'm probably
really going to regret not adding a print statement.

Ed


Site Timeline