Sign up ×
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.

For the LFSR mod 2, determine the degree of m and maximum sequence length

s_(i+3)≡ s_i+s_(i-2)+s_(i-4) mod 2

determine the degree of m and the maximum sequence length.

I can get the degree of $m$ easily by taking $2^{(m -1)}$, but I am confused about getting the degree of $m$. I don't even know what this is referring to here. Any help?

share|improve this question
Could you add (via an edit) what you’ve been trying so far? That’ld surely help to provide helpful answers. – e-sushi Oct 22 at 16:06
Your sentences are contradictory. "I can get the degree of m easily", and "confused about getting the degree of m" at the same time? Is m the minimal polynomial of the recurrence? – kodlu Oct 22 at 23:08
I think you mean the degree of the feedback polynomial, right? – Cryptostasis Oct 23 at 18:28

1 Answer 1

Let $i+3=j$ so your recurrence becomes $s(j)=s(j-3)+s(j-5)+s(j-7)~mod~2.$ The degree of the corresponding connection polynomial is $7$ and the polynomial itself is $c(x)=1+x^3+x^5+x^7.$ If the polynomial is primitive, then the period of the resulting LFSR sequence with nonzero initial state is $2^7-1=127.$ However this polynomial is not even irreducible since it is $(x+1)(x^6+x^5+x^2+x+1)$ modulo 2. Thus your sequence will not be maximum period. Depending on the initial conditions it will be generated by either $x+1$ or the degree 6 factor. The degree 6 polynomial turns out to be primitive, however.

share|improve this answer

Your Answer


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.