GCL

本题考查 LCG 相关分析。

FLAG 转数字得到 m。 素数 $p$ ，两随机数 $a,b$ ，序列 $\{s_n\}$ 满足关系：$$s_{n}=as^{-1}_{n-1}+b;\pmod{p}$$ gift 给了连续 10 项 s，我们需要求出下一项作为 key 解密 c=m^key

和 LCG 类似，我们肯定要先求出 $p$ 出来。

$$\begin{array}{rl}{s}_i& =a{s}_{i-1}^{-1}+b(\mathrm{mod}p)\\ s_i{s}_{i-1}& =a+b{s}_{i-1}(\mathrm{mod}p)(\mathrm{消}\mathrm{掉}\mathrm{模}\mathrm{逆})\\ s_{i+1}{s}_i& =a+b{s}_i(\mathrm{mod}p)(\mathrm{再}\mathrm{写}\mathrm{一}\mathrm{项})\\ s_{i+1}{s}_i-s_i{s}_{i-1}& =b(s_i-s_{i-1})(\mathrm{mod}p)(\mathrm{消}\mathrm{掉}a)\\ s_i(s_{i+1}-s_{i-1})& =b(s_i-s_{i-1})(\mathrm{mod}p)(\mathrm{整}\mathrm{理}\mathrm{一}\mathrm{下})\\ s_{i+1}\ast (s_{i+2}-s_i)& =b(s_{i+1}-s_i)(\mathrm{mod}p)(\mathrm{再}\mathrm{写}\mathrm{一}\mathrm{项})\end{array}$$

交叉相乘把 $b$ 消掉：

$$s_i(s_{i+1}-s_{i-1})(s_{i+1}-s_i)-s_{i+1}(s_{i+2}-s_i)(s_i-s_{i-1})=0(\mathrm{mod}p)$$

求 GCD 可以求出 $p$ (也可能是倍数)，之后也可以求出 $b,a$