Re: Penrose (Was: Infinities)
Hal Finney (hal@rain.org)
Mon, 10 Nov 1997 10:21:58 -0800
Wayne Hayes, <wayne@cs.toronto.edu>, asks:
> Hal Finney <hal@rain.org> writes:
> >There are pseudo random number generators which are believed to be
> >indistinguishable from true random number generators even with all the
> >computing power in the entire universe (by some definition).
>
> Do you have a reference for this? The best ones that I've heard of
> that are purely algorithmic are the well-known linear congruential
> ones.
Actually, there are much better ones. I am referring to cryptographically
strong random number generators. See a good crypto text, such as
Schneier's "Applied Cryptography", chapters 16 and 17. Section 17.9
describes some generators which are provably as difficult as solving hard
problems like factoring and discrete logarithms. These are believed
(but not proven) to be computationally intractable for modestly sized
numbers of a few thousands or tens of thousands of bits.
Hal