On Mon, Apr 18, 2005 at 05:45:58PM -0700, "Hal Finney" wrote:
> On Apr 11, 2005, at 11:11 PM, Russell Standish wrote:
> > I'm dealing with these questions in an artificial life system - Tierra
> > to be precise. I have compared the original Tierra code, with one in
> > which the random no. generator is replaced with a true random
> > no. generator called HAVEGE, and another simulation in which the RNG
> > is replaced with a cryptographically secure RNG called ISAAC. The
> > results to date (and this _is_ work in progress) is that there is a
> > distinct difference between the original Tierra PRNG, and the other
> > two generators, but that there is little difference between HAVEGE and
> > ISAAC. This seems to indicate that algorithmic randomness can be good
> > enough to fool learning algorithms.
>
> It definitely should be. At least certain types of cryptographic random
> number generators are reducible to factoring. That means that if any
> program can distinguish the output from the crypto RNG from the output
> of a true RNG, you could factor a large number such as an RSA modulus.
> This would be an important and completely unexpected cryptographic result.
>
> Assuming that factoring is truly intractable, crypto RNGs are as good
> as real ones, and deterministic universes are indistinguishable from
> nondeterministic ones.
>
> Hal
This was exactly the point Sasha Wait made when I presented these
results at ALife 9. However the argument doesn't quite hold, because
I've never claimed that my procedure was computationally feasible (in
fact it strikes me that my algorithm is NP-hard, however that doesn't
stop me throwing lots of supercomputer grunt at it!). It is always
possible to factor large numbers, its just that it is assumed to be
computationally infeasible.
However, in another sense the point is valid. Complexity is in the
"eye of the beholder", and the "beholder" will have limited
computational capability, and probably unable to distinguish between
true randomness and sufficently strong cryptographic sequences.
Cheers
--
*PS: A number of people ask me about the attachment to my email, which
is of type "application/pgp-signature". Don't worry, it is not a
virus. It is an electronic signature, that may be used to verify this
email came from me if you have PGP or GPG installed. Otherwise, you
may safely ignore this attachment.
----------------------------------------------------------------------------
A/Prof Russell Standish Phone 8308 3119 (mobile)
Mathematics 0425 253119 (")
UNSW SYDNEY 2052 R.Standish.domain.name.hidden
Australia http://parallel.hpc.unsw.edu.au/rks
International prefix +612, Interstate prefix 02
----------------------------------------------------------------------------
- application/pgp-signature attachment: stored
Received on Tue Apr 19 2005 - 19:48:05 PDT