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?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
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$)

Improve this answer
$\endgroup$
4
  • $\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, 2015 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, 2015 at 5:48
  • $\begingroup$ By the way, proper names don't normally go between quotation marks. $\endgroup$
    – fkraiem
    Jun 16, 2015 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, 2015 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}$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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