/*
* Galois linear feedback shift register (LFSR) (Java)
*
* Copyright (c) 2021 Project Nayuki
* All rights reserved. Contact Nayuki for licensing.
* https://www.nayuki.io/page/galois-linear-feedback-shift-register
*/
import java.math.BigInteger;
import java.util.Random;
/**
* Galois LFSR random number generator. This can be used in place of java.util.Random.
* In this class, a polynomial is represented as a BigInteger, where the coefficient of
* the xk term is represented by bit k.
*/
public final class LfsrRandom extends Random {
/*---- Demo program ----*/
public static void main(String[] args) {
LfsrRandom r = new LfsrRandom(BigInteger.valueOf(0x16801), BigInteger.valueOf(1));
r.printDebug();
for (int i = 0; i < 30; i++)
System.out.printf("%08x%n", r.nextInt());
r.printDebug();
}
/*---- Instance members ----*/
private final BigInteger characteristic;
private final int degree;
private BigInteger state;
/**
* Constructs an LFSR with the specified characteristic polynomial and initial state polynomial.
* The characteristic polynomial must have degree at least 2. The state polynomial must have degree
* less than the degree of the characteristic polynomial, and must not be the zero polynomial.
* @param charistic the characteristic polynomial
* @param state the initial state polynomial
* @throws NullPointerException if any argument is {@code null}
* @throws IllegalArgumentException if the polynomials do not satisfy the requirements
*/
public LfsrRandom(BigInteger charis, BigInteger state) {
if (charis.signum() == -1)
throw new IllegalArgumentException("Invalid characteristic polynomial - negative");
if (charis.bitLength() < 2)
throw new IllegalArgumentException("Invalid characteristic polynomial - degree too low");
if (state.equals(BigInteger.ZERO))
throw new IllegalArgumentException("Invalid state polynomial - all zero");
if (state.bitLength() >= charis.bitLength())
throw new IllegalArgumentException("Invalid state polynomial - degree >= char poly degree");
characteristic = charis;
degree = charis.bitLength() - 1;
this.state = state;
}
@Override public boolean nextBoolean() {
boolean result = state.testBit(0); // Use bit 0 in the LFSR state as the result
state = state.shiftLeft(1); // Multiply by x
if (state.testBit(degree)) // If degree of state polynomial matches degree of characteristic polynomial
state = state.xor(characteristic); // Then subtract the characteristic polynomial from the state polynomial
return result;
}
@Override protected int next(int bits) {
int result = 0;
for (int i = 0; i < bits; i++)
result = (result << 1) | (nextBoolean() ? 1 : 0);
return result;
}
public void printDebug() {
System.out.printf("characteristic: degree=%d poly = %s%nstate: degree=%d poly = %s%n",
degree, polynomialToString(characteristic), state.bitLength() - 1, polynomialToString(state));
}
private static String polynomialToString(BigInteger poly) {
StringBuilder sb = new StringBuilder();
boolean head = true;
for (int i = poly.bitLength() - 1; i >= 0; i--) {
if (poly.testBit(i)) {
if (head) head = false;
else sb.append(" + ");
sb.append("x^" + i);
}
}
return sb.toString();
}
}