# Given occasional LFSR samples can the next sample be computed?

Suppose I have access to an LFSR generator output used in a radio communications system, with the LFSR being used to authenticate devices. The system cycles an internal unknown length LFSR (greater than 32 bits) an unknown but constant number of times and returns the truncated upper 32 bits, with the lower bits being unknown.

I do not know the starting condition or the polynomial, but I can read the truncated output from this system as it transmits. Using this data alone, can I predict the next output using an algorithm such as Berlekamp-Massey algorithm?

I know that Berlekamp-Massey can solve given 2n captured bits, but do these have to be completely consecutive, or can they be a scattered "picture" of the output? Do I need to know the size of the generator to use Berlekamp-Massey?

I'm thinking of implementing this in a communications system: power consumption and complexity is key here, and an LFSR uses considerably less power and flash memory than a full AES or SHA authentication system, but I'm not sure if it will be easy to predict. (The idea is the receiver will refuse to acknowledge packets an incorrect LFSR, preventing the device being "impersonated".)

Firstly, many $k-$decimations $s_{kt}$ of LFSR sequences (those with $gcd(k,2^n-1)=1$) are shifted LFSR sequences themselves so this can be used for prediction.
If you can find a template $T=\{0,t_1,\ldots,t_{n-1}\}$ (with $0<t_1<t_2<\cdots<t_{n-1}$ such that the samples you have of the LFSR sequence $(s_t)$ cover $n+1$ shifts of this template you can set up a linear system and solve for the recurrence. In fact assuming $n=3$ one can (Berlekamp Massey is more efficient of course, this would need Gaussian elimination) set up the system
$$c_0 x_t + c_1 x_{t+1} + c_2 x_{t+2}=x_{t+3}\\ c_0 x_{t+1} + c_1 x_{t+2} + c_2 x_{t+3}=x_{t+4}\\ c_0 x_{t+2} + c_1 x_{t+3} + c_2 x_{t+4}=x_{t+5}$$
and solve for the LFSR coefficients $c_i$. For the template I mentioned, a similar system needs to be solved. This case is the template $T=\{0,1,2\}$ with shifts also $\{0,1,2\}.$