Re: PRNG Breaking

From: George Marsaglia (
Date: 09/21/04

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

"Jean-Luc Cooke" <> wrote in message
> 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:

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
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

George Marsaglia