Project Nayuki

Galois linear feedback shift register

A linear feedback shift register (LFSR) is a mathematical device that can be used to generate pseudorandom numbers. Here we will focus on the Galois LFSR form, not the Fibonacci LFSR form. Its setup and operation are quite simple:

  1. Pick a characteristic polynomial of some degree \(n\), where each monomial coefficient is either 0 or 1 (so the coefficients are drawn from \(\text{GF}(2)\)). (For example, \(x^{10} + x^7 + x^0\).)

  2. Now, the state of the LFSR is any polynomial with coefficients in \(\text{GF}(2)\) with degree less than \(n\) and not being the all-zero polynomial.

  3. To compute the next state, multiply the state polynomial by \(x\); divide the new state polynomial by the characteristic polynomial and take the remainder polynomial as the next state.

  4. Every time a state is generated, treat the coefficient of the \(x^0\) monomial term as a generated pseudorandom bit. (Using the coefficient of any other term is also fine, as long as it is at a fixed position for the LFSR.)

  5. In software, each polynomial is represented as a list of coefficients – in fact, a bit string. There is no need to keep track of \(x\)’s and powers.


Source code

The implementation is optimized for clarity, not for speed. The polynomials are represented in bitwise little endian: Bit 0 (least significant bit) represents the coefficient of \(x^0\), bit \(k\) represents the coefficient of \(x^k\), etc.

More info