6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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 :-) $\endgroup$ – Voo Jul 4 '14 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.