Understanding how Prime Polynomials are applied to LFSRs? In doing some research on LFSRs I understand that a primitive polynomial can determine what taps to be used to create an LFSR that has as many bits as the degree of the polynomial that will cycle through all non-zero states. E.G. A primitive polynomial whose coefficients are in GF(2) such as $x^4+x^3+1$ implies that a 4 bit LFSR will cycle through every possible non-zero state once and only once if the 4th bit and the 3rd bit are used as taps.
I don't understand the connection between a primitive polynomial and the taps of an LFSR. I never would have looked at a primitive polynomial and thought "let's make those bits in a register and xor them... etc" and made the connection. Can somebody explain this magic?
 A: To understand the connection between the taps and Primitive Polynomials, it is important to look into Galois Field or Finite field in depth. However, I would try to summarise it: 
LFSR circuit basically performs multiplication on a "field". A field usually defined as set with two operations defined ( multiplication and additions) and other laws such as associative and distributive laws hold. 
Finite fields are called Galois Field such Binary numbers (0 and 1) with XOR (= modulo 2 addition) and AND (multiplication) is a GF(2). 
Polynomials with binary coefficient also form a GF(2) with each term (x^n) either present(1*x^n) or absent (0*x^n). Addition and Multiplication of these polynomials forms a field: Add (= XOR of each term) and Multiply (Shifting to the left). 
 
A primitive polynomial is one that cannot be factored. And as a fact: for any degree there is exists at least one prime polynomial ( Look for Primitive Polynomial Table). 
Taking the result of the above multiplication, and modulo a prime polynomial, we can form GF(2^n). 
As an example: 
Consider a 4 bit LFSR with polynomials x^4 + x + 1. With LFSR=> 

The Pattern it generates : 0001, 0010, 0100, 1000, 0011, 0110, 1100, 1011 .... 
Notice that whenever MSB (Q4) is one, the current register values are xored with "10011" or if its zero, the values are only shifted left. 
This can also be explained in terms of primitive elements: 
a^3 = 1*x^3 + 0*x^2 + 0*x^1 + 0*x^0 
a^4 = 1*x^4 xor x^4 + x + 1 = x + 1 = "0011"
In summary : 
Galois Field Multiplication => Shift left in Hardware
Taking the result mod p(X) => Xoring when MSB is 1
Hope this helps. 
Source: Compilations from Study notes from University of Munich and Berkeley. 
