The Solina's paper Generalized Mersenne Numbers contains a Linear Feedback shift register I am not able to understand. Here it is:

enter image description here

It is supposed to be a normal Linear Feedback shift register but it doesn't seem to follow the "normal" lfsr rule. Is anyone able to explain the logic it follows?

  • $\begingroup$ The definition of $f(t)$ is given as $f(t) = t^3 - t + 1$, while the table lists the values $1,\ t,\ t^2$. Is that supposed to be that way? $\endgroup$ – Ella Rose Feb 2 '18 at 15:22
  • $\begingroup$ @ella Rose well that is the original paper see page 4. $\endgroup$ – Antonio Sanso Feb 2 '18 at 15:27
  • $\begingroup$ It does indeed appear to be listed that way in the paper, never mind. $\endgroup$ – Ella Rose Feb 2 '18 at 15:27

I'm not sure I understood your question correctly, but what Solinas is doing is shifting the input polynomial by multiplying it by $t$ and reducing modulo $f(t)$

To compute the reduction it subtracts $f(t)=t^3-t+1$. So, for example, after shifting the first line (where shifting means multiplication by $t$) what you obtain is: $t^3$ from which you subtract the modulus, so $t^3-t^3+t-1=t-1$ which is what you obtain in the second row.

And so on for the other rows.

In the table, the top row identifies the constant term, degree-1 term, and degree-2 term of the polynomials, while the second row (-1,1,0) identifies the value used for the modular reduction. The third row is the initial value of the LFSR which is $t^2$ by Solinas' construction.

|improve this answer|||||
  • $\begingroup$ This is correct. The action of shift registers over GF(2) ( this one is over the integers) can be represented in an equivalent way. $\endgroup$ – kodlu Mar 12 '18 at 21:28

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.