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.