From: Scott Brickner <sjb@austin.ibm.com>
Date: Fri, 25 Aug 95 15:22:53 PDT
To: Sam Quigley <poodge@econ.Berkeley.EDU>
Subject: Re: random coincidences
In-Reply-To: <199508250707.AAA14271@quesnay.Berkeley.EDU>
Message-ID: <9508252222.AA14188@ozymandias.austin.ibm.com>
MIME-Version: 1.0
Content-Type: text/plain


Sam Quigley writes
>What are some of the more common "coincidences" and non-random
>correlations that ordinary random number generators (ones found in
>common computer languages that don't take extensive measures to be
>random) have?

The most common one is "linear correlation" between successive
random values.  The typical PRNG supplied with compilers is what's
called a "linear congruential random number generator", which has
something like:

    S0 = (user supplied seed)
    Sn+1 = ( a * Sn + b ) mod c
    Rn = f(n)

The choice of constants a, b, and c are critical to the process.
A decent practical discussion is in "Numerical Recipes in C".

If you take N successive random numbers and interpret them as a
point in an N-dimensional space, then the points generated by the
linear congruential PRNG don't tend to fill up the space as they
would in the "true" random case.  They tend to lie on N-1 dimensional
planes instead, and when a, b, and c are chosen poorly, sometimes
*very* few such planes.

>It seems that there's a lot of fuss about getting very random numbers,
>but unless the numbers produced by ordinary measures have very obvious
>coincidences, maybe it's a big fuss about nothing...?

If NetScape uses such a PRNG to select 40bit keys for SSL, then the
work to be done in brute-force search going on right now might be
*significantly* reduced by knowing the planes on which the numbers
lie.  If the constants are particularly poor, there might be as little
as ten or twelve bits of real key.  You could search that on a *Newton*
in less than an hour or so --- nevermind the MasPars and such being used
in the current project.