# Cracking linear congruential generator knowing a, b, m and scaled numbers

I was reading the book "Cryptographic engineering", one of the variation of linear congruential formula is as follow: $X_n = a_1X_{n-1} + a_2X_{n-2} \pmod {2^{31}-1}$

$a_1$ and $a_2$ are two prime numbers respectively

Given 50 scaled consecutive number $[s_{1}, s_{2}, ... s{50}]$, is there an efficient way to work backward?

If brute forcing is used, it will need to go through $2^{64}$ numbers.

What would be the efficient way to solve the formulas?

• Solve it like any other system of linear equations. The extended euclidean algorithm can compute multiplicative inverses which you need to use where you'd use normal division when working with rationals/reals. – CodesInChaos Mar 2 '17 at 9:14
• Hint: suppose you're given $X_n$ and $X_{n-1}$ and this was an ordinary equation of the real numbers, how would you recover $X_{n-2}$? – SEJPM Mar 2 '17 at 12:00

Given an equation (for any modulus $Y$)
$$X_n = a_1 X_{n-1} - a_2 X_{n-2} \mod Y$$
$$X_{n-2} = a_2^{-1}(a_1 X_{n-1} - X_n) \mod Y$$
So with $X_n,X_{n-1},a_1,a_2$ you can calculate $X_{n-2}$ directly. Furthermore: $a_2^{-1}$ is not division in the real numbers, but the multiplicative inverse in a finite group / ring, also called modular multiplicative inverse. If $a_2$ is coprime to $Y$, this inverse exists.