Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Do all $2^{\ell}$ (where $\ell$ is the bit length of the shift register) states always occur in a LFSR or can I choose my taps badly so some states are skipped and the period is shortened?

If so is there a way to prove the number of states that can occur in a LFSR?

share|improve this question
    
Found some info that you might find interesting: cryogenius.com/software/lfsr –  mikeazo Dec 13 '12 at 14:05
add comment

2 Answers

up vote 5 down vote accepted

As fgrieu points out, the number of states reached is at most $2^\ell-1$ and that is achieved only if the feedback polynomial is a primitive polynomial (and the initial state is not all zero). If the feedback polynomial is irreducible but not primitive, then with nonzero initial loading, the LFSR state will cycle through $N$ states, where $N$ is a divisor of $2^\ell-1$ but not a divisor of $2^m-1$ for any $m$ that is itself a proper divisor of $\ell$. For example, if the feedback polynomial is an irreducible but nonprimitive polynomial of degree $6$, then, depending on which polynomial is being considered, the LFSR will cycle through $21$ states, or through $9$ states. The $63$ nonzero states form $3$ cycles of $21$ states each, or $7$ cycles of $9$ states each. Depending on the initial loading, the LFSR will cycle through one of these cycles (and the other cycles will never occur).

For an arbitrary feedback polynomial, which could be reducible, that is, factorable into a product of (not necessarily distinct) irreducible polynomials (meaning something like $[f(x)]^2g(x)$ might be the factorization), the answer is much messier and complicated to describe. Search for the term period of a polynomial and read Lidl and Neiderriter's Finite Fields or Chapter 6 of Berlekamp's Algebraic Coding Theory for some of the details.

share|improve this answer
add comment

Read chapter 6 of the HAC.

It will tell you that no, the $2^ℓ$ states are never reached, at most $2^ℓ-1$ are. And that occurs for taps chosen per a primitive polynomial, and initial state not all zero.

For lists of primitive polynomials, I use jj's useful and ugly page of mathematical data.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.