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.

It is clear that when we have any output stream $x_0,x_1,...$ produced by linear feedback shift register than this output has to be periodic.

Now I was wondering if we can find an upper bound for the period of the output sequence from a linear feedback shift register with $R$ registers over $\mathbb F_q$?

share|improve this question
    
What does a linear feedback shift register with $R$ registers mean? In general, the period of a polynomial $g(x)$ is the least integer $e$ such that $g(x)$ divides $x^e -1$. If $g(x)$ is the feedback polynomial of an LFSR, then $e$ is the upper bound you seek. But determining $e$ for a given $g(x)$ is by no means a trivial task. –  Dilip Sarwate Nov 26 '13 at 3:58
    
With $R$ registers I mean, that each of them contain one value from the finite field $\mathbb F_q$. Initially these contain the values $x_0,...,x_{R-1}$ which is called the initial fill. At each time step, the values in the registers are shifted down and the final register is filled by a new value determined by the old values in all of the registers. I hope this explains the term. –  TI Jones Nov 26 '13 at 4:04
    
When the LFSR reaches a state it has been in before, what happens to the output sequence? How many possible states are there? Now you have an upper bound. –  K.G. Nov 26 '13 at 7:57

1 Answer 1

up vote 1 down vote accepted

Between them, K.G. and Dilip Sarwate have pretty much answered your question. That is, you can derive an upper bound using the method described by KG:

When the LFSR reaches a state it has been in before, what happens to the output sequence? How many possible states are there? Now you have an upper bound

However, working out how tight this bound is can be much more difficult (as per Dilip's comment):

In general, the period of a polynomial $g(x)$ is the least integer $e$ such that $g(x)$ divides $x^e−1$. If $g(x)$ is the feedback polynomial of an LFSR, then $e$ is the upper bound you seek.

In particular, this is the cycle generated if you initialize the LFSR with all the entries $0$ except for the last one set to $1$.

For a good LFSR, the period will be close to the maximum possible. Consider the tightness of the bounds described by K.G.: if the feedback polynomial is 'badly' chosen (for example $x^k-1$), the period may be much lower.

Since each time you 'step' the LFSR you are multiplying by $x$ within the appropriate field extension, to calculate the period it doesn't matter where on the cycle you start. It does matter that your initial condition is somewhere on this cycle, as for example initializing with the $0$ state leads to a cycle of only $1$ element. Now, if the period is maximal, then every non-zero element must be part of the 'main' cycle, and so any initialization vector will lead to an LFSR of maximal period. However, if the period is lower than this, we must be careful to ensure that the starting vector is indeed on the main cycle.

share|improve this answer
1  
You should use $x^k-1$ as the extreme example of bad feedback polynomials. –  K.G. Nov 26 '13 at 10:14
    
Ah yes sorry, careless error. That said, $x-1$ certainly wouldn't lead to a good LFSR! :P –  figlesquidge Nov 26 '13 at 10:17
    
One think that is not 100% clear; In the case that the upper bound is achieved, why is it then achieved by any non-zero initial vector? –  TI Jones Nov 26 '13 at 10:21
    
That better? :/ –  figlesquidge Nov 26 '13 at 10:32

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.