Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 '15 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 '15 at 23:08
I think you mean the degree of the feedback polynomial, right? – Cryptostasis Oct 23 '15 at 18:28

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
@ComputerScienceStudent does this answer your question? If so, please accept it. – kodlu Feb 2 at 12:12

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.