Past exam of the mathematics course of the University of Cambridge 2009 ii Paper 4 4H Solution 2026-10-14
A general feedback shift register of length over an alphabet stores , outputs , and shifts to for a fixed function . When the alphabet is a field , it is a linear-feedback shift register if is linear over , equivalently for fixed coefficients in . The binary case uses the finite field ; the examples and counterexamples below are binary.
For a genuinely nonlinear example take length three and . Its values at and are both zero, but its value at their sum is one, violating additivity. Thus this general register is not linear. It even has an invertible state update: from the old leading bit is , so the counterexample does not rely on allowing singular registers.
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 4 3K Solution Created 2026-09-23 Updated 2026-09-25
A general binary feedback shift register of length has stateand a feedback function . One update outputs the oldest bit, shifts the state, and insertsThe initial fill is . It is a linear-feedback shift register whenfor fixed .
The Berlekamp-Massey algorithm reads an intercepted sequence from left to right while maintaining the shortest connection polynomial that reproduces the prefix. At each new symbol it computes the discrepancy between the observed bit and that predicted by the current recurrence. A zero discrepancy leaves the polynomial unchanged; a nonzero discrepancy adds a suitably shifted copy of the connection polynomial saved at the previous increase in linear complexity. After at least twice the unknown register length, it recovers the shortest recurrence, after which the entire keystream can be predicted.
Applying those discrepancy updates toreturns the connection polynomialEquivalently, the sequence obeysIndeed this predicts successively . No recurrence of length one or two fits the prefix, so its linear complexity is three.