# How many bits are needed for an LFSR to generate a specific number of sequences?

I need to generate 64-bit data sequences 16 times pseudorandomly. How many bits should the linear-feedback shift register (LFSR) have in order to do so?

That is, what is the number of bits for the initial seed? How can I calculate this number? Can we minimize this number? Should it be a fixed number of bits?

• Welcome to CryptographySE. Is this a homework question? – kelalaka Feb 17 at 8:48
• I don't know alot about LSFRs and Pseudo random bit generators but I need the answer of this question because I have to use it in my research. – eHH Feb 17 at 8:51
• An LFSR with $L$ length can generate $2^L-1$ periodic sequence. With a given $2L$ key stream of the generated stream, one can produce the LFSR with its tap position in $\mathcal{O}(n^2)$-time by Berlakamp-Massey Algorithm. Using only LFSR is not a good idea. – kelalaka Feb 17 at 9:20
• In the above, $n$ is $L$. Also, if the taps are known, $2L$ becomes $L$, the algorithm becomes more trivial, and the run time drops to $\mathcal{O}(L)$. In most use cases, a lone LFSR only give a false sense of cryptographic security. – fgrieu Feb 17 at 9:40
• Yes. $n=L$. If you tell more about your actual problem, like where are you going to use these 16 pseudo bits, you can find more specific help four your cause. – kelalaka Feb 17 at 9:46

An $$n$$-bit LFSR with a primitive feedback polynomial will cycle through all $$2^n-1$$ possible non-zero states. You will need an LFSR to generate $$16\times 64 = 1024$$ bits. An 11-bit LFSR will cycle through $$2^{11} - 1 = 2047$$ states and output as many bits, so for your purposes, an 11-bit state is sufficient.
If the feedback polynomial is not primitive, then the period will be unpredictable but not maximal. An example primitive polynomial suitable for use in a maximal-length 11-bit LFSR is $$x^{11}+x^9+1$$.
It's extremely important to know that an LFSR is not cryptographically secure. An $$n$$-bit LFSR can be broken after only $$n$$ bits of keystream are known ($$2n$$ bits if the feedback polynomial is secret).