Re: PRNG Breaking

From: George Marsaglia (geo_at_stat.fsu.edu)
Date: 09/21/04


Date: Tue, 21 Sep 2004 15:01:30 -0400


"Jean-Luc Cooke" <jlcooke@engsoc.org> wrote in message
news:cipj03$7vf$1@driftwood.ccs.carleton.ca...
>
> Papers have been written stating that *any* LFSR (and I can only assume
> that this applies to all linear PRNGs) PRNG can be broken with a small
> number of outputs.
>
> I can't find the paper right now, sorry, but here's some discussion
> allong the same idea:
> http://www.ciphersbyritter.com/NEWS5/MACLAR.HTM
>

Since points
                 (x_i, x_{i+1},...,x_{i+k}),
coordinates successive values from a congruential RNG,
fall on a lattice, it is easy to find the a,k and m for the generator
       x_{i+1} = a*x_i+k mod
that produces segments of the sequence. Usually half a dozen 3-tuples will
serve.
I have used this method since I established that lattice structure
in the 1960's, and you will find a recent description with an
example and a test problem in
    http://tbf.coe.wayne.edu/jmasm/vol2_no1.pdf

George Marsaglia