LFSR for small numbers with large periods I want to generate a few random numbers using an LFSR. However, the LFSR output depends on the number of taps, so for a large period I use large (relative) number of bits. This causes the numbers to be as large as the period. For example, I would like to use a 16-bit LFSR to generate random 5-bit numbers. What is the proper way to reduce the number of bits but still ensure that single numbers don't repeat and that the sequences don't become shorter?

[Edit:]

For degree 5, I am using the polynomial x^5+x^3+1 and the following code:

lfsr = (lfsr &gt;&gt; 1) ^ (-(lfsr &amp; 1u) &amp; 0x0014u); 


For n = 16, I am using the polynomial  x^16 + x^14 + x^13 + x^11 + 1

lfsr = (lfsr &gt;&gt; 1) ^ (-(lfsr &amp; 1u) &amp; 0xB400u);  


Are any of these a problem?
Contrary to what's stated in the question and its comments, extracting any $m\le n$ bits from the sequence of the states of an $n$-bit LFSR still result in a sequence with period $2^n-1$, assuming the state of the $n$-bit LFSR is not zero and its generating polynomial is primitive. Proof sketch: by a fundamental property of LFSR with primitive feedback polynomial, its period has $2^n-1$ states not including the all-zero state. It follows that any bit has period $2^n-1$ with $2^{n-1}$ ones and $2^{n-1}-1$ zeroes.

Further, the sequence is as closely evenly distributed as an $m$-bit sequence of period $2^n-1$ can be: each of the $2^m$ values is reached $2^{n-m}$ times, except $0$ which is reached $2^{n-m}-1$ times. In fact, that's much too evenly distributed to be random.

Hence taking (say) the low 5 bits of a maximal-length 16-bit LFSR will result in a sequence with period 65535, and during that period each of the 32 values will be reached 2048 times, except 0 reached 2047 times. However that's NOT going to make even a passable non-cryptographic RNG: if the LFSR uses the Fibonacci construct, 4 bits of any output directly come from the previous output, and the situation is hardly better with a Galois construct (or not at all, depending on polynomial). For example, using the 16-bit generator in the updated question (which, per the convention I favor, use the polynomial $x^{16}+x^5+x^3+x^2+1$ rather than its reflexion $x^{16}+x^{14}+x^{13}+x^{11}+1$)

#include &lt;stdio.h&gt;
int main(void){
  unsigned x = 1, j = 128, y; // initial sate, number of outputs, output
  do {
    y = x&amp;31;
    printf("%02X%c", y, --j&amp;15?' ':'\n');
    x = x&gt;&gt;1 ^ 0xB400&amp;-(x&amp;1);
  } while(j);
return 0;}


we get this:

01 00 00 00 00 00 00 10 08 14 1A 0D 16 0B 05 02
01 00 10 08 04 02 11 08 14 0A 05 02 11 18 0C 16
1B 1D 1E 0F 17 1B 0D 16 0B 15 1A 0D 16 0B 05 02
11 08 04 12 19 1C 1E 0F 17 0B 05 12 19 1C 0E 17
1B 1D 0E 07 03 01 10 18 1C 0E 17 1B 1D 1E 0F 07
13 09 14 0A 05 12 19 1C 0E 07 13 19 1C 1E 1F 1F
1F 1F 1F 0F 07 13 09 14 1A 1D 0E 07 03 01 10 18
1C 1E 1F 0F 07 13 09 04 12 09 14 0A 15 1A 1D 1E


and it is painfully apparent that the right hex digit of any output is always the previous output right-shifted by 1.

One possible solution to that is to steps the LFSR $m$ times for each output of $m$ bits, collecting 1 bit at each step. One problem is that when $\gcd(m,2^n-1)\ne 1$ the period is reduced by that factor (and the proof of even distribution no longer works).

Rather, I formerly proposed to output y = ((0x6D9B*x+0xDB75)&amp;0xFFFF)&gt;&gt;11. It does improves things, but some of the problem with y = x&amp;31 remains: the distribution of two consecutive outputs is quite poor. Something like y = 0x6D9B*x, y = (y&lt;&lt;4 ^ y)*0xDB75, y = (y&lt;&lt;2 ^ y)&gt;&gt;11 &amp; 31 further improves things, while provably keeping the period and uniform distribution (because, until the &gt;&gt;11 &amp; 31 steps, the transformation from the low 16 bits of x to the low 16 bits of y is a mapping).

Caution: even perfecting that by using an even more complex transformation of output, the resulting sequence is not cryptographically strong, by any measure, and can't be made so without much more state bits.