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"?