Predicting PRNG given some of its previous output I a have a question about PRNGs and this is my very first experience with them. I have the following generator that takes a 56-bit seed $p$ during initialization and then chooses both $X$ and $Y$ randomly from the interval $[0, p]$.

Every time it is called, it returns the output of the next function:

def next(self):
    self.x = (2*self.x + 5) % self.p
    self.y = (3*self.y + 7) % self.p
    return (self.x ^ self.y)


I have the first 9 outputs of the generator and I need to predict the next output.

prng_output = [210205973, 22795300, 58776750, 121262470, \
           264731963, 140842553, 242590528, 195244728, 86752752]


I have thought of the solution which turned out to be correct by very slow, so apparently there must be another way to solve it.

My solution was to constrain the range of values for $p$ according to the given output. Also, generate all values for $X$ and for every value of $X$, calculate the first 9 values according to the previous equation and XOR it with the output to get $Y$. Finally, check of the sequence of $Y$s is valid or not (also according to the previous equation).

After some reading I learned that a reduced state (reduce the number of bits) of the generator can be determined.

So my question is how to crack the given generator, what is the "reduced state" of the generator, and how can I use that "reduced state"?
I'm not familiar with the terminology "reduced state", so I can't address that half of the question.

However, this particular PRNG makes it easy to reconstruct the internal state; we note that the state function can be rewritten as:

x := 2*x + 5 - kx * p
y := 3*y + 7 - ky * p


for some small integers $k_x$, $k_x$ (in fact, $0 \le k_x \le 2$ and $0 \le k_y \le 3$.  Once we do that rewrite, we notice that the lower bits no longer depend on the higher bits.

So, what we can do is:


Iterate over the possible $k_x$, $k_y$ values used to generate the second, third and fourth outputs; a total of 1728 possibilities.
For each set, we go through the possibilities for bit 0 of p and the initial x (note: because the initial y can be immediately deduced from the x and the first output, we don't have to iterate through that)
Check to see if there's a combination that gives the bit 0's on the second, third and fourth outputs that we have; if there is, then start looking through the various possibilities for bit 1 of p and initial x.


When we manage to get through all 29 bits, and get all the bits of the output we observed, then we have the answer (and in fact, continuing the generate outputs will, in this case, continue to generate the listed outputs).

Going through the above procedure gives us the answers p = 295075153, x0 = 89059908, y0 = 164204369, next output = 231886864