0
$\begingroup$

I need to crack this linear congruential generator.

I have

$$X_{n+1}=a⋅X_n +b \pmod m$$

I know: $m=31,X_3=30,X_4=19,X_5=26$

How can I find $a,b$ and $X_0$?


I have got already the following equations:

$$26=a \cdot 19+b \pmod{31}$$

$$19=a \cdot 30+b \pmod{31}$$


substruct 2 equations to get

$$7= -11 \cdot a \pmod{31}$$ $$7= 20 \cdot a \pmod{31}$$

the inverse of 20 is 14 in $\bmod 31$, $20 \cdot 14 = 1 \pmod{31}$.

$$7 \cdot 14= 14 \cdot 20 \cdot a \pmod{31}$$

$$7 \cdot 14= a \pmod{31}$$

$\endgroup$
  • $\begingroup$ Welcome to Cryptography. I don't see what you have tried here, but the name is the hint: When you put given values you will get equations to solve. put $n=3$ and put $n=4$ $\endgroup$ – kelalaka Jan 8 at 18:41
  • $\begingroup$ Yes, I have edited the question $\endgroup$ – Antoshka Jan 8 at 18:51
  • $\begingroup$ Now, substruct the two equations side by side to get rid of $b$ and solve for $a$ $\endgroup$ – kelalaka Jan 8 at 18:54
  • $\begingroup$ So I receive: 7=16a mod(31) is it correct? $\endgroup$ – Antoshka Jan 8 at 19:00
  • $\begingroup$ nope $(26-19) = (19-30) a $ $\endgroup$ – kelalaka Jan 8 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.