With computer efficient linear feedback shift register

摘要

A fast pseudo-random number generator, which can be employed in a variety of systems such as a stream cipher cryptosystem or a Monte Carlo simulation system, includes a linear feedback shift register (LFSR) having a state contained in N storage elements storing N bits of binary data which are separated into w words having word length M. At least two tap sources provide binary data, each tap source has a number of bits which is a multiple of M. The LFSR also includes a linear feedback function coupled to tap sources and providing a temporary value which is a linear function, such as bit-wise exclusive-or, of the binary data provided from the tap sources. The LFSR state is advanced by shifting the binary data in the storage elements by a multiple of M bits and provide the temporary value to fill in storage elements that would otherwise be empty from the shifting.