patternMinor
Find missing value in period of LCG
Viewed 0 times
findperiodvaluelcgmissing
Problem
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.
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.
Solution
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:
-
Randomly pick a set of taps (a feedback polynomial).
-
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.
-
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.
-
Randomly pick a set of taps (a feedback polynomial).
-
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.
-
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.
Context
StackExchange Computer Science Q#28197, answer score: 6
Revisions (0)
No revisions yet.