# Linear Feedback shift register over integers

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

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?

• 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? – Ella Rose Feb 2 '18 at 15:22
• @ella Rose well that is the original paper see page 4. – Antonio Sanso Feb 2 '18 at 15:27
• It does indeed appear to be listed that way in the paper, never mind. – 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.
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.