3
$\begingroup$

I was reading about the Linear Feedback Shift Registers and I am confused about the technique to find the period of a primitive polynomial. Consider the polynomial $x^5 + x^2 + 1$. As this is a primitive polynomial, it should be a maximal period LFSR. Its period should be $2^5 - 1 = 31$. However, when I tried to generate a pseudo random sequence from this, the period turns out to be $15$.

enter image description here

01 -> 11111           32 -> 01111
02 -> 01111           33 -> 10111
03 -> 10111           34 -> 01011
04 -> 01011           35 -> 10101
05 -> 10101           36 -> 11010
06 -> 11010           37 -> 01101
07 -> 01101           38 -> 00110
08 -> 00110           39 -> 10011
09 -> 10011           40 -> 01001
10 -> 01001           41 -> 00100
11 -> 00100           42 -> 00010
12 -> 00010           43 -> 10001
13 -> 10001           44 -> 11000
14 -> 11000           45 -> 11100
15 -> 11100           46 -> 11110
16 -> 11110           47 -> 01111
17 -> 01111           48 -> 10111
18 -> 10111           49 -> 01011
19 -> 01011           50 -> 10101
20 -> 10101           51 -> 11010
21 -> 11010           52 -> 01101
22 -> 01101           53 -> 00110
23 -> 00110           54 -> 10011
24 -> 10011           55 -> 01001
25 -> 01001           56 -> 00100
26 -> 00100           57 -> 00010
27 -> 00010           58 -> 10001
28 -> 10001           59 -> 11000
29 -> 11000           60 -> 11100
30 -> 11100           61 -> 11110
31 -> 11110          

1, 111101011001000, 111101011001000, 111101011001000, 111101011001000, 11 

What is the correct period of this sequence? Is it 15 or 31?

$\endgroup$
2
$\begingroup$

I believe that you're evaluating the feedback polynomial incorrectly; both in your diagram, and in the chart you have listed, it would appear that you have a feedback polynomial similar to $x^5 + x^4 + x$ (note: there are a couple of different ways to turn a feedback polynomial into an LFSR; I'm not sure which one you're intending to use).

To fix your diagram, one way to fix it is if you place the taps at $b_3$ and $b_1$ (not $b_5$ and $b_2$)

$\endgroup$
  • $\begingroup$ As per "Applied Cryptography" by "Bruce Schneier" (section 16.2) , for a (5,2,0) polynomial you need to tap at $b_5$ and $b_2$. You mentioned that there are different ways to turn a feedback polynomial into a LFSR, could you please shed some light on different techniques to do this? $\endgroup$ – CryptoNovice Jun 16 '15 at 4:46
  • $\begingroup$ The feedback polynomial of this generator is $x^5+x^4+x$ to me as well (see here for how I define it). By the way, in your example you find that $(1,1,1,1,1)$ never occurs again, this should tell you that something is wrong. $\endgroup$ – fkraiem Jun 16 '15 at 5:48
  • $\begingroup$ By the way, proper names don't normally go between quotation marks. $\endgroup$ – fkraiem Jun 16 '15 at 6:48
  • $\begingroup$ @poncho and @ fkraiem, can you please show the detailed steps involved in converting the primitive polynomial (5,2,0) into maximal length LFSR on this page as it would also help others looking for an answer to this question. (1) How did you arrive at the feedback polynomial $x^5 + x^4 + x$? (2) How to find the tap sequence for this polynomial such that its period would be maximized? (For the primitive polynomial (3,1,0) tapping at 3 and 1 gives maximum LFSR. For (4,1,0) tapping at 4 and 1 gives maximum LFSR. But the same logic fails for (5, 2, 0)). $\endgroup$ – CryptoNovice Jun 17 '15 at 12:05
2
$\begingroup$

Its period is 31. You add a new bit to the leftmost side. Hence you need to sort as $x^4$ $x^3$ $x^2$ $x$ $1$ from left to right. Add $x^2$ $(3. term)$ and $1 (5. term)$.

$x^4$ $x^3$ $x^2$ $x$ $1$

$$\mathtt{11111, 01111, 00111, 00011, 10001, 11000, 01100, 10110, 11011, 11101,\\ 01110, 10111, 01011, 10101, 01010, 00101, 00010, 00001, 10000, 01000,\\ 00100, 10010, 01001, 10100, 11010, 01101, 00110, 10011, 11001, 11100,\\ 11110, 11111}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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