# 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 >> 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?

-
I don't understand the first requirement - why shouldn't those smaller numbers repeat? And since they must not repeat, doesn't this sort of imply the period needs to be reduced to $2^5$ from $2^{16}$, contradicting your second requirement? –  Thomas Jan 16 '13 at 7:27
I see what you mean, but you said "single numbers don't repeat" which would imply you are looking for a pseudorandom permutation of $\mathbb{Z} / 2^5 \mathbb{Z}$ (which can be achieved using a Fisher-Yates shuffle using the 16-bit LSFR). Just truncating off bits wouldn't work here, obviously. Or did I misunderstand you? What you want is, to convert a 16-bit pseudorandom permutation to a 5-bit pseudorandom permutation, am I correct? –  Thomas Jan 16 '13 at 7:34
Let me explain with a shorter one. Lets say I have 2 bit numbers and the sequence goes something like 0 2 1 3 0 2 1 3,... I don't want it to keep doing 0213, i want it to keep changing 0 2 1 3, 2 0 3 1, ... –  Gustavo Litovsky Jan 16 '13 at 21:25
Understood, so you want to switch to a different permutation when the first one is exhausted and so on. Do you have memory requirements? Can you store up to 32 values for a shuffle? –  Thomas Jan 16 '13 at 21:34
@D.W.: Of course the application here can't be cryptography. However I can understand the perspective of the OP that considerations on the period of a subset of the state of an LFSR are on the right side of topicality, for LFSRs definitely are used in cryptography, e.g. in the respectable ASG. –  fgrieu Jan 18 '13 at 10:09

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.

-
Thanks for your comment. I am using Galois construct for the LFSR. The sequence doesn't need to be cryptographically strong. –  Gustavo Litovsky Jan 16 '13 at 23:28
I have taken your suggestion to pick the lower 5 bits of the stream. It contradicts your assertion. The period is 32. I am plotting the histogram (it shows uniform distribution) and also plotting the numbers sequentially and they repeat exactly every 32 samples. Perhaps your notation was incorrect. I would have expected that selecting m <= n bits results in period (2^m)-1 not (2^n)-1. –  Gustavo Litovsky Jan 16 '13 at 23:38
I tried your suggested y=..., but the results have a period of 32, the are not uniformly distributed (many numbers are missing) and some of them repeat one after the other. –  Gustavo Litovsky Jan 16 '13 at 23:51
@gl3829: No idea, what you're doing wrong, but fgrieu is obviously right. Try to pick the lower 1 bit. According to you you'll get a period of two, but it must be just like described in the second paragraph. Moreover, for any $m<n$ there's no number missing. I'd guess your LSFR is wrong. –  maaartinus Jan 17 '13 at 5:16
@gl3829: I also guess your LFSR is wrong. Try generating the 16-bit LFSR with state=((-(state&1))&0x8016)^(x>>1); . That's using the primitive polynomial $x^{16}+x^{14}+x^{13}+x^{11}+1$ and the Galois construct. Insert 0x0 before - if your compiler barks. –  fgrieu Jan 17 '13 at 6:49

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.

-
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.

-
Perhaps you should "adjust your response" to answer the question. If you want to vote to close, then vote. Question is not off topic. LFSR is clearly very relevant to cryptography and the question can help others, even if my use of it not be considered cryptography. There is no other forum here that will suit the question better. –  Gustavo Litovsky Jan 18 '13 at 6:10
Thank you for the feedback, @gl3829. I did answer the cryptographic part of the question: see my suggestion in paragraph 3 of my answer, for my answer. Of course, you have to recognize that sometimes the best answer takes a different form that you may have expected or hoped for. By the way, my question stands: What are your security requirements? Are you using this for cryptographic purposes? I don't think we can answer the question suitably without knowing what the security requirements are (if any) for the output of this generator. –  D.W. Jan 18 '13 at 7:36