How to crack a Linear Congruential Generator (LCG)

Question

The full question is: How to crack a Linear Congruential Generator when a, c and m in the LCG formula. I googled this question and I found what I wanted:

here is the question: https://brilliant.org/problems/breaking-linear-congruential-generators/

and here is the screenshot of the answer (you need to make an account, to see the answer):

https://imgur.com/a/RrxEU

The problem is that I don't understand the answer.

1.) I do not understand this equation from the answer (what is this equation and why is it used): $$Z_n = Y_nY_{n+2}- Y^2_{n+1}$$

2) And I don't understand how a and c are found afterwards.

Any help is apprecciated

Also I am aware that there are other methods to solve this question for example by using a matrix: Calculation for linear congruential generator: Setting up equations

Thank you

Answer 1

Just use the formulas in the picture.

Part 1: With $Y_n \equiv a Y_{n-1} \pmod m$ you get
$$Y_{n+1} \equiv a Y_{n} \equiv a^2Y_{n-1} \pmod m$$ $$Y_{n+2} \equiv a Y_{n+1} \equiv a^3Y_{n-1} \pmod m$$ and therefore $$Z_n \equiv Y_{n}Y_{n+2} - Y_{n+1}^2 \equiv (a\cdot a^3 - (a^2)^2) Y_{n-1} \equiv 0 \pmod m$$

Thus $Z_n = m\times z_n$ is a multiple of $m$ and (as claimed in the image) for a sufficient number of samples $\{X_n\}$ the gcd of corresponding $Z_n$ is expected to be $m$.

---

Part 2: If you accept $m := 1000000007$ from the gcd calculation the two linear $$a X_1 + b \equiv X_2 \pmod m$$ $$a X_2 + b \equiv X_3 \pmod m$$ congruences can be solved as follows: First compute the modular multiplicative inverse $(X_1-X_2)^{-1} \equiv 560056067 \pmod m$ (this is usually done with the Extended Euclidean Algorithm or Euler's theorem, see Wikipedia, for single values you can use an online calculator, e.g. https://planetcalc.com/3311/ with the input $X_1-X_2 = 587411898, m=1000000007$ or with Wolfram Alpha solve (720555190-133143292)x = 1 mod 1000000007) and then $$a \equiv (X_2-X_3) (X_1-X_2)^{-1} \equiv 782674123\times 560056067 \equiv 1664525 \pmod m$$ $$b\equiv X_2 - a X_1 = 133143292 - 1664525\times 720555190 \equiv 13904216 \pmod m$$ This is done like the solving of a usual system of linear equations. Subtract the second from the first equation and get $a$ $$aX_1 - a X_2 \equiv a(X_1-X_2)\equiv X_2-X_3 \pmod m$$ $$a \equiv (X_2-X_3)(X_1-X_2)^{-1} \pmod m$$ and $b$ from the first equation.