Pseudorandom Blast from the Past


A friend was messing around with pseudo-random number generators, so I dug this thing up from the historical archives for him.

It's a PRNG implementation done while I was a university student.

The main idea is simple: run multiple Galois-configuration m-sequence LFSRs in parallel, combining their outputs with XOR, thus making an LFSR with a longer sequence than would be possible by running an LCG in the given machine architecture. This is possible because the m-sequences are all co-prime (the length in bits of each individual component LFSR is a Mersenne exponent).

There are several defects: it's not cryptographically secure, nor does it pass Marsaglia's Diehard test battery nor the more modern Dieharder. The LSB is always even. However, it still might be "good enough" for some kind of embedded use, or to be used as a starting point for something better.

The example implementation has a period of about 2\^93, using eight 32-bit values as the internal state and eight bit-masks. The implementation is also quite simple.

Grab it here: lfsr-prng.tar.gz.

The implementation consists of two parts; prng.c contains the actual PRNG, and prngdriver.c exercises the PRNG to output values in some format. As an example it now outputs things in Dieharder-format.

The description from prng.c using my own words (I removed my old mail address):

/* Simple PRNG using a linear feedback shift register (LFSR)  
 * in Galois configuration.  
 *  
 * A primitive polynomial modulo 2 is used for LFSR taps.  
 * Thus each LFSR outputs an m-sequence. The length (in bits)  
 * of each LFSR is a Mersenne exponent. Thus the length of  
 * the m-sequence is a prime number (2^m-1).  
 *  
 * Since the individual periods are relatively prime, the output  
 * period length of LFSR generator combination is the product  
 * of individual LFSR period lengths:  
 *  
 * (2^2-1) * (2^3-1) * (2^5-1) * (2^7-1) * (2^13-1) * (2^17-1)  
 * * (2^19-1) * (2^31-1) = about 2^96.34  
 *  
 * This PRNG was intended for use with machines without /dev/random  
 * (eg. old DOS boxes found from parent's place etc.)  
 *  
 * NOTE: This generator is not good for cryptographical applications!  
 */

Have fun with it!