LFSR for small numbers with large periods

Question

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 >> 1) ^ (-(lfsr & 1u) & 0x0014u); 

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

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

Are any of these a problem?

Answer 1

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 <stdio.h>
int main(void){
  unsigned x = 1, j = 128, y; // initial sate, number of outputs, output
  do {
    y = x&31;
    printf("%02X%c", y, --j&15?' ':'\n');
    x = x>>1 ^ 0xB400&-(x&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)&0xFFFF)>>11. It does improves things, but some of the problem with y = x&31 remains: the distribution of two consecutive outputs is quite poor. Something like y = 0x6D9B*x, y = (y<<4 ^ y)*0xDB75, y = (y<<2 ^ y)>>11 & 31 further improves things, while provably keeping the period and uniform distribution (because, until the >>11 & 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.

Answer 2

I will add a few points worth considering to @fgrieu's answer.

The output sequence of period $2^n-1$ from a $n$-bit maximal length LFSR has the property that it contains runs of zeroes and ones in (close to) the correct proportions. In particular, there is one run of $n$ consecutive ones (no run of $n$ consecutive zeroes, but there is one run of $n-1$ consecutive zeroes. So, consider what happens if you are using $m$ consecutive bits extracted from the LFSR contents. As the long sequence of consecutive ones (or zeroes) is passing through these $m$ positions, your $m$-bit random number generator will be stuck in the $111\cdots 1$ (or $000\cdots 0$) state for $n-m$ consecutive clock cycles ($n-m-1$ consecutive clock cycles). The LFSR output also contains shorter runs of $k$ bits, and for $k > m$, these shorter runs will also cause the output of the $m$-bit random number generator to be stuck in the same state for $k-m$ consecutive clock cycles.

So, while globally your $m$-bit random number generator will have a good distribution, with each of the $2^m-1$ nonzero random numbers occurring $2^{n-m}$ times and $000\cdots 0$ occurring $2^{n-m}-1$ times, the local behavior is not good at all, with $000\cdots 00$ and $111\cdots 1$ occurring several times in a row, not just once but at lots of different places in the period of $2^n - 1$.

References:

A. Lempel and H. Greenberger, "Families of Sequences with Optimal Hamming Correlation Properties," IEEE Trans. Inform. Theory, vol. IT-20, January 1974.

D. V. Sarwate and M. B. Pursley, "Hopping Patterns for Frequency Hopped Multiple Access Communications," IEEE International Communications Conference: Conference Record, Vol. 1, 1978.

D. V. Sarwate, "Reed-Solomon Codes and the Design of Sequences for Spread-Spectrum Multiple-Access Communications," Reed-Solomon Codes and Their Applications, (S. B. Wicker and V. K. Bhargava, eds.), IEEE Press, 1994.

Answer 3

1. If you are using this for cryptographic purposes, do not use a LFSR.

   Using a LFSR for pseudo random number generation is highly insecure.

   Instead, you should use a standard cryptographic PRNG, such a /dev/urandom. You can just repeatedly read bytes from /dev/urandom and keep just the low 5 bits. This will provide a very large period (essentially infinite, for all practical purposes) and will retain its cryptographic strength.

2. On the other hand, if you are not using this for cryptographic purposes, the question is off-topic here and should be closed.

Let us know which is the case so we can adjust the question and responses appropriately.