Linear Feedback Shift Register (LFSR)

2n-1 non-null sequences

• -1 non-null sequences if one of them has a 2n-1 period length, then all have it.

Primitive feedback functions (primitive polynomials)

• All non-null sequences have a 2 n–1 period length.

Issue

If you know N consecutive bits of the output, you know the entire sequence ahead.

The output must be mixed with something else ...

Generators using many LFSR: A5/1 (GSM)