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:
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\).)
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.
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.
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.)
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.
Properties:
The zero state will keep generating the zero state, which is why we must reject it.
In the best case, the state will have a cycle length of \(2^n - 1\). This is highly desirable.
To build an LFSR with the maximal cycle length, all these conditions together are necessary and sufficient:
\(x^{2^n-1}\) modulo the characteristic polynomial equals \(x^0\).
For each \(k\) such that \(k < n\) and \(k\) is a factor of \(2^n - 1\), \(x^k\) modulo the characteristic polynomial does not equal \(x^0\).
Fast skipping in \(Θ(\log k)\) time can be accomplished by exponentiation-by-squaring followed by a modulo after each square.
Source code 
- Java implementation: LfsrRandom.java
- Python implementation: lfsrrandom.py
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.