Re: "All random number generators eventually exhibit periodicity"?????

From: Paul Rubin (//phr.cx_at_NOSPAM.invalid)
Date: 07/27/04 

Date: 27 Jul 2004 11:38:59 -0700

Guy Macon <http://www.guymacon.com> writes:
> That *is* an interesting question. It relates to the "P" in "PRNG."
> We all know that a PRNG isn't a RNG (Thus the "Pseudo"), and doesn't
> give a random output but how far from random are we willing to go?
> does a 4-Bit LFSR qualify as a PRNG?

I think PRNG is supposed to mean about the same thing as a PRF from
concrete security, that is, a function from N to {1,0} that can't be
distinguished from random by any P-time computation. Thus, it's
unknown (because of the P vs NP question) whether there's truly any
such thing as a PRNG. But there are some functions that appear to be
PRF's, as far as we can "experimentally" tell.

Relevant Pages