LCG Recovering Parameters

Process

For a LCG defined as $S_{n+1}=a{S}_n+b\mathrm{mod}m$

Recovering m

• Define $t_n=S_{n+1}-S_n$
• $u_n=|t_{n+2}\ast t_n-t_{n+1}^2|$
• $m=gcd(u_1,\dots ,u_k)$, usually $k\ge 10$

Recovering a

• Recover $a$ as $t_i=a\cdot t_{i-1}\mathrm{mod}m$

Recovering c

• Recover $c$ as $S_{i+1}=a\cdot S_i+c\mathrm{mod}m$