Linear Feedback Shift Register

A linear feedback shift register is a Feedback Shift Register with linear i.e.

for some

The feedback (auxilary) polynomial is

Ordinary Generating Function

Theorem

The stream comes from a linear feedback shift register with auxiliary polynomial if and only if its Ordinary Generating Function is formally of the form with such that

Lemma

Let and be outputs from LFSRs of lengths , Then:

1. is output of LFSR of length
2. is output of LFSR of length Problem with is that there will be more on average.