# Find missing value in period of LCG

It's well known that linear congruential generators have a full period only if a few properties are fulfilled.

Now I need a LCG that does not generate a full period in 2^32 (easy to find, just violate one requirement) and I need one of those values in the period that's not used.

Is there any clever math trick/algorithm to find such a thing? I can see the obvious bruteforce solution, but that'd take quite some time and tons of memory - also it seems like an interesting math problem. I did check Knuth but he obviously focuses on showing how to get a full period.

PS: For people wondering - I have to trick a compiler into making sure it can't use DCE on some values and this seems like a very performant and hard to figure out way to achieve this.

Actually, bruteforce should work just fine. You can quickly find a set of taps that doesn't have a full period, then find a value that's not in the period. Here's what I'd do:

1. Randomly pick a set of taps (a feedback polynomial).

2. Verify whether this has a single full period of size $2^{32}-1$, as follows. Randomly pick a starting state $s_0$ (not the all-zeros state). Iterate forward starting from $s_0$, and see whether you get back to $s_0$ within at most $2^{32}-1$ steps. In this way, you can compute the period after starting from $s_0$. If this period is $2^{32}-1$, go back to step 1.

3. Now you have a LFSR and a starting state $s_0$, such that the full period is less than $2^{32}-1$; next you want to find a state $t$ that is not within the set of states reachable from $s_0$. Here's one way to do that:

• Randomly pick 10 states $t_1,t_2,\dots,t_{10}$. These will be your 10 candidates for $t$. Initially, each of them is unmarked.

• Now run the LFSR forward, starting from $s_0$, until you get back to $s_0$. At each step compare the current state of the LFSR to $t_1,t_2,\dots,t_{10}$. If the current state of the LFSR is equal to $t_i$, then mark $t_i$.

• At the end, when you get back to $s_0$, look at which of the $t_i$ are marked. If one of the $t$'s is unmarked, say $t_j$, then you are done: you have a LFSR feedback polynomial and a starting state $s_0$ such that you know $t_j$ is not within the period of values starting from $s_0$. If all of the $t_i$'s are marked, go back to step 1.

How long will this take? Probably about $2^{32}$ operations. I would expect at least $1/2$ of the choices of feedback polynomials to lead to a LFSR with less than full period, so you shouldn't have to repeat steps 1-2 too many times (on average about 2 times). Each repetition takes $2^{32}$ operations.

Now once you find a good LFSR, where $s_0$ does not lead to a full period, then the period that's reachable from $s_0$ will be on average about $2^{31}$ or smaller. Thus, step 3 will take about $2^{31}$ operations. Also, this means that about $1/2$ of all possible states will be unreachable. Therefore, with probability $1-1/2^{10}$, at least one of your 10 candidates for the $t$'s will be good, so the chances that you have to repeat step 3 is very low.

So, this is probably good enough. This is easy to code up and will probably finish within a few hours or less.

There are cleverer things you can do, but they probably don't make sense in practice. You could spend a bunch of hours thinking hard to write tricky code, to save an hour or two of CPU time -- that's not a good tradeoff.

Nonetheless, since it sounds like you appreciate the math and clever tricks, here are the tricks you could use to make this more efficient. Let $p(x)$ be the feedback polynomial for your LFSR. If $p(x)$ is reducible, then the LFSR will certainly not be full period. In other words, if $p(x)$ factors as $p(x)=q(x) r(x)$, the LFSR won't be full period. So, you could start by picking two polynomials $q(x),r(x)$ randomly of suitable degree (their degrees must sum to 32, and neither should be a constant), then use their product as the feedback polynomial.

Now once you have a feedback polynomial, there are efficient algorithms to check whether a state $t$ is reachable from starting state $s_0$. This basically becomes a discrete logarithm problem in $GF(2^{32})$, which can be solved very efficiently. See, e.g., https://crypto.stackexchange.com/q/17970/351. That said, you wouldn't want to implement those algorithms for this problem. They are overkill, and much harder to implement than the simple bruteforce approach I outlined above.

If you want to make the problem easier, you could use a maximally factored feedback polynomial, such as $p(x)=(x+1)^{32} = x^{32} + 1$. Now the all-ones state has a period of 1, i.e., it repeats forever. So, you can take $s_0=111\cdots 1$ and $t$ to be anything else. This is a bit of a trivial example, so it might not be what you are looking for.

• "Actually, bruteforce should work just fine" - oh definitely, I wrote a bruteforce program after asking this question in a rather similar vein to what you propose (I assumed it'd take a few hours to run too, but we were both wrong by an order of magnitude.. was pretty quick surprisingly). But you're absolutely right that I appreciate the math much more - it's fun to learn new concepts :-)
– Voo
Jul 4 '14 at 22:41