Period of a pseudo-random sequence generated using an LFSR I was trying to generate maximal length pseudo random sequence using an linear feedback shift register (LFSR).
I have read from many sources that the length of the pseudo random sequence generated from the LFSR would be maximum if and only if the corresponding feedback polynomial is primitive. 

I have tried to generate the pseudo random sequence for the primitive polynomial (4,1,0) (corresponding to polynomial $x^4 + x + 1$) by tapping at bits 4 and 1, and it has resulted in a sequence with a period of $2^4$ - 1 = 15. Similarly I have tried primitive polynomial given by (3, 1, 0) (corresponding to polynomial $x^3 + x + 1$) by tapping at bits 3 and 1 and it has resulted in a sequence of period $2^3$ - 1 = 7. 

When I tried to apply this same logic to the primitive polynomial (5, 2, 0) (corresponding to polynomial $x^5 + x^2 + 1$) it yields a sequence with period 15. While it should have yielded a sequence with period 2^5 -1 = 31. Following is the circuit diagram for (5, 2, 0)



1) What is the exact procedure to convert the given polynomial into a maximal length LFSR? 

2) How do I determine the correct tap bits for a given polynomial?
The LFSR that you give is really of length $4$ rather than $5$, since $b_1$ never gets used. The correct way to implement a "Fibonacci" LFSR is explained in the Wikipedia article: $b_1$ should be the leftmost bit rather than the rightmost bit.

There is also an alternative kind of LFSR knows as a "Galois" LFSR, also described in Wikipedia, which is dual to a Fibonacci LFSR: at each point, the contents of the register is shifted, and if the bit which is shifted out is 1, then a mask is XORed to the contents. In both types of LFSR, the resulting sequence has maximum period iff the feedback polynomial is primitive.



The polynomials that you give as examples are known as trinomials, polynomials with three non-zero monomials. Not all trinomials are primitive. There are algorithms for deciding whether a trinomial, or any other polynomial, is primitive. As far as I know, there is no explicit construction of primitive polynomials.

How do we test whether a given polynomial $P$ of degree $n$ is primitive? The first step is verifying that it is irreducible. The second step verifies that $x^{(2^n-1)/p} \not\equiv 1 \pmod{P}$ for every prime divisor $p$ of $2^n-1$ – this step requires factoring $2^n-1$. A list of primitive polynomials can be found on Wikipedia.