Andrew
Reputation
Top tag
Next privilege 250 Rep.
 Oct 30 awarded Nice Question Oct 20 awarded Notable Question Jan 31 awarded Popular Question Apr 1 awarded Scholar Apr 1 accepted Predicting values from a Linear Congruential Generator Mar 18 revised Predicting values from a Linear Congruential Generator deleted 268 characters in body Mar 15 awarded Supporter Mar 15 comment Predicting values from a Linear Congruential Generator You are of course right! I misunderstood which bits you were referring to. I simplified the algorithm with the assumption that n is not a power of two in the original question. Your second procedure will work for n=6 - nice work. How many values are required to know with certainty the future values? Mar 14 comment Predicting values from a Linear Congruential Generator new Random(1L<<40) and new Random(1L<<41) have entirely different sequences modulo 8 yet the 20 rightmost bits of the seed are the same. Just tried it :) Mar 14 comment Predicting values from a Linear Congruential Generator The low-order bits of seed are discarded by the bitshift, so I assume you mean only the 20 left-most (high-order) bits have any influence on the output in the first example? This is untrue. Mar 14 comment Predicting values from a Linear Congruential Generator It is not enough to know just part of the seed to predict all future output as you suggest. Two seeds identical except for the 'top' bits might give the same result when these bits are shifted out, but will give different sequences thereafter. The part that is shifted out will affect future values and therefore must be known. Mar 14 revised Predicting values from a Linear Congruential Generator added 13 characters in body Mar 14 comment Predicting values from a Linear Congruential Generator You're right - I want to understand why though. So far I haven't been able to find an algorithm anywhere with the two conditions listed above that breaks it. I wouldn't use it in practice in any case :) Mar 14 comment Predicting values from a Linear Congruential Generator Can you possibly explain the second part in more depth? I'm not sure I follow what you are doing. Mar 14 comment Predicting values from a Linear Congruential Generator The low-order bits never have an opportunity to influence the output of the generator, which for the purpose of predicting the output behaves as a 20-bit (not 48-bit) state. The low-order bits are not used in the output, but they affect the next output - changing the low-order bits will change the high-order bits and hence the output from the next seed. This means bruteforcing high-order bits is not sufficient. Mar 13 comment Predicting values from a Linear Congruential Generator Thanks, I have changed the modulus to 6 since it need not be a power of two - not sure if this makes a difference. Mar 13 revised Predicting values from a Linear Congruential Generator edited body Mar 13 revised Predicting values from a Linear Congruential Generator edited body Mar 13 awarded Student Mar 13 awarded Editor