From: wet!naga (Peter Davidson)
Date: Sat, 19 Jun 93 16:53:37 PDT
To: cypherpunks@toad.com
Subject: testing pseudorandom number generators
Message-ID: <m0o78nY-0003XYC@wet.uucp>
MIME-Version: 1.0
Content-Type: text/plain



 
Tyler Yip, UnixWeenie(tm), asks:
 
>What characteristics of the multiplier and modulator provide large periods?
 
The standard reference is D. Knuth, The Art of Computer Programming
(as I recall), Volume II, the chapter on random numbers.  Knuth
gives conditions involving a, k and m for n = ( n*a + k ) mod m
to have a long (or maximal) period.
 
For the less mathematically-inclined, a pleasing and quick way to
eliminate weak pseudorandom number generators is to use the generator
to pick row and column pixel positions on a graphics screen.  Turn
on "randomly" selected pixels.  If the screen does not get completely
filled in a visibly random way then the generator is weak.  A particularly
weak generator will turn on 1% or so of the pixels then nothing further
happens because it has entered a cycle.  A weak generator may fill the
screen with parallel lines.  Writing a program to test generators in this
way is a useful, easy and amusing task and is left as an exercise for the
reader.
 
Someone may be inclined to reply that this test does not show that a
generator is cryptographically strong, to which the answer is: 
True, but it certainly eliminates the ones that aren't, and it's 
fun to watch the pixel display for different generators.

Well, on second thought, maybe some generators that are not crypto-
graphically bullet-proof might pass this test.  But if some generator
does not, you can throw it away immediately.