本文基于 Sugar_fan 的 Hacking Incorrect XOR Hashing with mt19937_64 。
最经典的场景是所谓的 $\texttt{XOR hashing}$ 。比如在一些题解里，会给每个对象分配一个随机值，然后把集合里的值全部异或起来作为哈希。直觉上，如果每个值都“很随机”，那么不同集合产生相同哈希的概率应该很小。但对于 $\text{mt19937\_64}$ ，这个直觉并不总是可靠。
mt19937 是什么
$\texttt{mt19937}$ 是基于 $\texttt{Mersenne Twister}$ 的伪随机数生成器。它不是“每次都重新算一个真正随机数”，而是维护一整块内部状态，然后不断把状态“搅动”并输出。
可以把它理解成两步：先更新状态，再从状态里取数并做一次变换。
内部状态与状态空间
它维护了一个长度为 $312$ 个 $64$ 位整数 的状态数组。所以它的状态总大小大约是：
$$312 \times 64 = 19968 \text{ bit}$$
其中真正有效的线性复杂度参数是 $19937 \text{ bit}$ ，这也是名字里 $19937$ 的来源。
状态转移：twist 的线性更新
当当前状态快用完时，它会对整个状态数组做一次“扭转($\texttt{twist}$)”更新，核心思路是：
- 取相邻的两个状态值
- 拼接它们的高位和低位
- 通过移位、异或、按位与、再异或一个常数矩阵参数
- 得到新的状态值
更具体地说，它会用类似下面的形式更新：
$$x_i \leftarrow x_{i+m} \oplus \text{some transform of }(x_i, x_{i+1})$$
这里的 $m = 156$ 。
$\texttt{transform}$ 会把高位、低位拼起来，再根据最低位是否为 $1$ 决定是否异或一个固定常数 $a$ 。
输出变换：tempering
拿到一个状态值后，$\text{mt19937}$ 不会直接输出，而是再做一次 temper（温和化） 处理，也就是一串位运算：
- 右移
- 左移
- 与常数掩码相与
- 再异或
这一串操作的目的，是让输出的低位、高位都更均匀一些。 对于 $\texttt{mt19937\_64}$，典型的 $\texttt{tempering}$ 形式是：
$$y = x\\ y \mathrel{\oplus}= (y \gg 29) \& 0x5555555555555555\\ y \mathrel{\oplus}= (y \ll 17) \& 0x71D67FFFEDA60000\\ y \mathrel{\oplus}= (y \ll 37) \& 0xFFF7EEE000000000\\ y \mathrel{\oplus}= y \gg 43$$
最后的 $y$ 就是输出。
seed 的作用
$seed$ 的作用为初始化内部状态，更直白一点地说：
- $seed$ 决定它一开始落在哪个状态上；
- 从这个初始状态出发，后面输出的整个随机序列就都被固定了；
- 同一个 seed，总是得到同一串输出；
- 不同 seed，通常得到不同的序列，但它们的生成规则仍然完全一样。
为什么 mt19937_64 可以被线性化
把内部状态和输出都看成 $\mathbb F_2$ 上的向量，也就是按位考虑 $0/1$ 。这样一来，$\texttt{mt19937\_64}$ 的状态转移和输出都可以写成线性变换。
设初始状态为 $x$，状态转移矩阵为 $A$，输出矩阵为 $B$，那么第 $i$ 次输出可以表示成
$$o_i = BA^i x.$$
这里的意思是：先把初始状态经过 $i$ 次状态转移，再从中取出输出。由于整个过程都是位运算，所以在 $\mathbb F_2$ 上是线性的。
这件事非常关键，因为一旦线性关系存在，就可能被我们利用。
从线性递推到恒为 0 的 XOR
如果存在一个非零多项式
$$p(t)=\sum_i a_i t^i$$
满足
$$p(A)=0$$
那么对输出做同样的线性组合，就有
$$\bigoplus_i a_i o_i= \bigoplus_i a_i BA^i x= B\left(\bigoplus_i a_i A^i\right)x= Bp(A)x= 0.$$
这说明，只要我们找到了这样一组系数 $a_i$，就能构造出一组固定位置的输出，它们的 $XOR$ 永远是 0，与 $seed$ 无关。
换句话说：随机数生成器虽然看起来在输出随机值，但它实际上服从某个线性递推；只要把这个递推找出来，就能制造“必然碰撞”。
如何恢复递推关系：Berlekamp–Massey
$\texttt{mt19937\_64}$ 的最小多项式阶数是 $19937$ 。一个常见做法是：
- 取某一位的输出序列，比如最低位；
- 取前 $2\times 19937$ 项；
- 用 $\texttt{Berlekamp–Massey}$ 算法恢复它的最短线性递推。
为什么这样做有效？因为 $\texttt{BM}$ 的作用就是：给定一个序列前缀，找出生成这个序列的最短线性递推式。对于线性复杂度不超过 $19937$ 的序列，前 $2d$ 项通常足以恢复出长度为 $d$ 的最短递推。
对 $\texttt{mt19937\_64}$ 来说，状态转移的设计目标就是达到最大周期，因此它的最小多项式阶数就是 $19937$ 。于是只要我们恢复出来的递推阶数也达到 $19937$ ，就基本可以认为已经拿到了完整的关系式。
为什么只看某一位就够了
任意非零线性投影得到的序列，其最短递推多项式都必须整除状态转移矩阵的最小多项式。
设状态转移矩阵为 $A$ ，初始状态为 $x$ ，取某一位等价于对输出做一个线性投影 $B$ 。于是得到标量序列
$$s_i = BA^i x.$$
如果这个序列满足某个非零递推多项式 $g(t)$ ，那么 $g$ 就是它的最短递推多项式。另一方面，$A$ 的最小多项式 $f$ 满足 $f(A)=0$ ，因此 $f$ 也会消去这个序列，所以有
$$g(t) \mid f(t)$$
对 mt19937_64 来说，$f$ 是不可约的，并且次数为 $19937$ 。因此 $g$ 只有两种可能：
$$g(t)=1 \quad \text{或} \quad g(t)=f(t).$$
其中 $g(t)=1$ 当且仅当这个投影得到的序列恒为 $0$ 。也就是说，只要我们选取的那一位不是恒零序列，就必然能通过 $\texttt{Berlekamp–Massey}$ 恢复出完整的最小多项式。
所以本质原因是，只要这位输出不是零序列，它就已经携带了整个状态转移的最小多项式信息。
这对 XOR 哈希意味着什么
很多题解会这么做：
- 给每个元素、点、边、颜色、区间端点等分配一个随机值；
- 用这些随机值的 $XOR$ 作为集合哈希；
- 认为“哈希为 $0$ ”就意味着某种特殊结构。
问题在于，如果这些随机值来自 $\texttt{mt19937\_64}$ ，那么它们并不是真正独立随机，而是线性相关的。只要我们恢复出了那组线性关系，就能选择一批随机值，让它们的 $XOR$ 恒等于 $0$ 。
这就能构造出碰撞，甚至让某些错误判定稳定发生。
实际攻击流程
攻击思路可以概括为三步。
收集足够多的输出
让程序按顺序生成足够多的随机数。
例如对最低位形成序列：
$$s_0, s_1, \dots, s_{39974}.$$
用 BM 恢复线性递推
对这段比特流运行 $\texttt{Berlekamp–Massey}$，得到一个递推多项式，对应一组系数 $a_i$，使得
$$\bigoplus_i a_i s_i = 0.$$
构造哈希碰撞
只要题目中的随机哈希恰好由这些输出构成，那么你就能安排输入，让程序最终异或出来的值正好落在这条线性关系上，于是哈希恒为 0。
uniform_int_distribution 为什么也未必安全
很多人会觉得：
我不用直接取
rng()，而是用uniform_int_distribution，这样总该安全了吧？
不一定。
原因是：某些标准库实现、某些特定区间下的实现路径，可能会让分布过程退化成对底层随机数的某种简单变换，比如取低若干位、做截断、或者使用与线性结构兼容的组合方式。这样一来，虽然表面上经过了分布器包装，但底层仍然保留了足够强的 $\mathbb F_2$ 线性痕迹，依然可能被同样的方法利用。
总结
$\texttt{mt19937\_64}$ 不是密码学随机数生成器。它的内部状态转移和输出映射都可以在 $\mathbb F_2$ 上看成线性变换，因此：
- 它的输出序列满足线性递推；
- 可以通过 $\texttt{Berlekamp–Massey}$ 恢复递推关系；
- 一旦拿到递推，就能构造出固定 $XOR$ 为 $0$ 的输出组合；
- 因而基于它的 $XOR$ 哈希并不可靠，特别是在可被对手观察或控制输出顺序的场景下。