A Fast Method of Generating Digital Random Numbers

Almost all methods of generating digital random numbers use as input a set of previously generated random numbers which were produced by an iterative arithmetic process (modulo a large integer)--e.g. Xn a F(Xn.x , Xn_2 , · · · , X,,_,)mod N with initial conditions i = Ci, X--2 = C*2 I n = 0, 1, · · · X.J = Cj . For each new random number, Xn, this arithmetic process is repeated. The integer N and the initial values Ci, C2, · · ·, Cj are chosen to * M r . Rader is with Lincoln Laboratories, Massachusetts Institute of Technology, Lexington, Massachusetts. Lincoln Laboratories is operated with support from the U. S. Air Force. 2303 2304 T H E BELL SYSTEM TECHNICAL JOURNAL, NOVEMBER 1070 guarantee a large period of repetition. Methods of the type described above involve a considerable propagation delay, representing at the least one addition or one multiplication time, between the time the nth random number is put into its storage register, and the time at which the (n + l)st random number is available. This delay is not generally a problem in most applications, because computational delays in other parts of most digital systems are far greater than those encountered in generating random numbers. However, it is conceivable that in the future a need will arise for which random numbers must be computed far more rapidly than is now necessary. With such a time in mind we propose the following algorithm, for which the time necessary to produce a new random number is equal to the sum of a flip-flop settling time, and the propagation delay of an exclusiveor gate.