random

[Alex Martelli]

"Mark 'Kamikaze' Hughes" <kamikaze at kuoi.asui.uidaho.edu> wrote in message
news:slrn9hi99k.9ns.kamikaze at kuoi.asui.uidaho.edu...
    ...
>   A true random number generator is not one that requires an infinite
> amount of information to predict, it is one that is *impossible* to
> predict, regardless of how much information you have.

<shrug> OK, that's your definition.  Do you agree with Ullrich's
apparent thesis that _any_ physical system is such a 'true random
number generator' because of inevitable quantum effect _no
matter at how macroscopic a level you look at the system_,
and secondarily that 'true randomness' (he calls it 'perfect')
only exists at all _because_ of quantum effects?  If so, then
I'm not really interested in pushing the debate much further
or splitting hairs between 'requiring an infinite amount of
information to predict' and 'impossible to predict regardless
of how much' (finite amount, presumably?) 'information you
have'.  As ANY experiment we can make runs on physical
systems (including possibly our minds), then true total
randomness, by this thesis, is ALWAYS present and there is
nothing we can do to remove it, so we might just as well
use some idiotic library rand() that LOOKS like it's a horrid
generator -- we cannot predict the next bit (it MIGHT come
from an intrinsically unpredictable flipping somewhere in a
transistor), thus it must be OK, right?

It's not right *FOR ME*: it is, in fact, utterly useless -- one
might just as usefully argue the solipsistic thesis that you're
all figments of my imagination, or whatever other such way
to waste one's time and others'.

If this is NOT what you mean, then let's find out what you
DO mean by "impossible to predict" if it's not some quantum
sophistry:-).  What about shuffling a deck of cards, spinning
a roulette wheel, or rolling dice?  These are the traditional
ways to generate randomness.  Are all of these a "true random
number generator" by your definition?  Couldn't I for example
in principle predict the outcome of dice being rolled, if I did
have a sufficient but finite amount of information on the
state of the dice?  There only seem to be macroscopic phenomena
involved -- in the same sense in which computer systems are
designed to eschew errors from unpredictable bitflipping, but
the dice have it easier, as they're rather more massive than
the typical tiny packet of particles used in a computer today.


> > Meanwhile I still see nothing 'sinful' in dealing with
> > randomness finitely,
>
>   It's simple.  If you have a pseudo-random number generator, you will
> eventually repeat,

If the 'eventually repeat' is sufficiently longer than the
time to the expected heat death of the Universe, for
example, is that a real problem?  Any more than it is
a real problem that "in theory" all particles on the seat
I'm sitting on MIGHT simultaneously and unpredictably
just happen to move one meter to the right and I'd have
a rather nasty fall thereby?  Expected time to such an
event is many times the expected time to the end of
the Universe, so I don't often worry about that.

> and other people, given the right information, can
> duplicate your random numbers.  This is, to put it mildly, not a good
> thing (the word "catastrophic" comes to mind in crypto applications).

I like the crypto 'adversarial' way of looking at randomness,
it seems quite fruitful.  So, suppose the intended application
IS a one-time pad for perfect cryptography -- it has to be
a finite amount of bits since I do have to transfer a copy of it
(and by costly secure channels too) to the intended recipient
before it's any use.  Now, what difference does it make whether
the bits in the pad are generated by using a system that is
_impossible_ to predict (sufficient amplification of some
tastefully chosen quantum effect, say -- assuming quantum
effects ARE indeed intrinsically unpredictable), or one that
WOULD be possible to predict EXCEPT for the little detail of
needing *a sufficiently large amount* of information that is
just not there?  N coin-flips, for example, to generate N bits.

Each flip is presumably predictable (with a probability as
close to 1 as one wishes) GIVEN information about initial
coin state and forces applied, that, besides being a LOT of
bits:-), was simply not recorded at the time -- it's not
around, that info.  How do you like that one-time pad now?

Now what, if anything, is different about using some program
implementing a given algorithm to generate the pad?  What
else except the amount of bits of information that are needed
for the prediction?  I.e., the amount of randomness.  If high
enough, if a large-enough number M of bits of information is
needed to predict the N bits on the pad, then the system is
as secure as with N coin-flips.  There is clearly no problem
with M being _FINITE_ -- only, quite possibly, with it being
_SMALL_.  So, I badly need to measure that M -- how else
can I reject too-weak solutions, if I can't measure how good
they are but only mutter ironies about M being finite anyway?


Alex