I was wondering if it is feasible to determine the number of iterations required for the Linear Feedback Shift Register algorithm to generate the sequence let's say"1010" from the initial seed "1001," without the need to iterate through all possible values, given that the polynomial used is (x^4 + x^3 + 1).
To be ohnest I don't even know where to start, so i'll be thankful for any help.
For the given polynomial X^4+X^3+1 the feedback function of the shift register is the register state is written as (x0,x1,x2,x3) at instant k
f(x0,x1,x2,x3)=x0+x2
Hence the state map of the shift register is
x0(k+1)=x1(k),x1(k+1)=x2(k),x2(k+1)=x3(k),x3(k+1)=x0(k)+x2(k)
From the well known Golomb's condition the shift register is non singular i.e. the state map has an inverse. The inverse is given by
x0(k)=x2(k+1)+x3(k+1), x1(k)=x0(k+1), x2(k)=x1(k+1), x3(k)=x2(k+1)
Hence the reversed orbit from the state 1010 is the sequence:
(1010)-->(1101)-->(1100)-->(0110)-->(1011)-->(0101)-->(1010)
Thus the orbit does not have the state (1001). Hence the state (1010) cannot be reached from (1001).
In this method the computation of inverse of the shift register state map is an algebraic computation and is feasible in polynomial time in n the number of states. The orbit computation starting from a given state can be exponential if the orbit length through the final state x(T) has exponential length. Otherwise the reconstruction of the orbit is of polynomial time of the order equal to the orbit length. Hence reachability can be found out without enumerating all trajectories of the state evolution