程序里经常会遇到一种看似朴素、实际很贵的问题：两个东西是不是一样？
它可能是两个字符串、两个文件、两个集合、一段文本里的子串，或者三个矩阵是否满足 \(A \cdot B = C\)。如果对象本身很大，尤其是在对象需要跨机器通信、被反复比较、以流式方式到达，或者比较结果只需要高概率可靠时，直接逐个字节比较往往不是最想要的方案。
随机指纹法处理的正是这类问题。它不试图完整保留对象，而是把对象映射成一个短得多的值，然后比较这些短值。这个短值可能丢失信息，所以它不是压缩意义上的可逆编码，而更像一个可快速比较的影子。
影子不能替代实体，但如果影子不同，实体一定不同；如果影子相同，实体也许相同，也许只是碰巧投在了同一个地方。随机性的作用，是让这种“碰巧”变得可控。
指纹和哈希函数有相似之处。设对象集合为 \(\mathcal{O}\)，我们从一组映射 \(\mathcal{H}\) 中随机选择一个函数 \(f\)，然后用 \(f(O)\) 作为对象 \(O\) 的指纹。对于两个对象 \(O_1\) 和 \(O_2\)：
第二点是关键。对于输出空间远小于输入空间的固定哈希函数，理论上总会存在碰撞；在非密码学场景下，如果对手知道函数，也可能针对性地寻找碰撞。随机选择函数后，对手很难提前知道我们会拿哪一把尺子去量对象。随机化并不是为了神秘，而是为了把最坏情况变成概率问题。
在算法分析里，能区分 \(O_1\) 和 \(O_2\) 的函数常被称为 witness，也就是“见证者”。如果某个 \(h \in \mathcal{H}\) 满足 \(h(O_1) \ne h(O_2)\)，那么 \(h\) 就见证了 \(O_1 \ne O_2\)。指纹法的设计目标，就是让见证者足够多，同时让每个指纹足够短。
这两个目标天然冲突。指纹越短，比较越快，通信越省，但碰撞空间也更大；指纹越长，错误概率更低，却离“直接发送原对象”越来越近。许多随机化算法的味道，就藏在这个 trade-off 里。
一切复杂对象都可以映射成二进制数，而一切二进制串又可以看成整数。给定 \(x \in \{0,1\}^n\)，令 \(\mathrm{Number}(x)\) 表示它对应的二进制整数。例如 \(1011_2\) 对应十进制的 \(11\)。
随机选择一个素数 \(p\)，定义：
\[\mathrm{Finger}_p(x) = \mathrm{Number}(x) \bmod p \]
这个定义非常朴素，但足够有力。如果有 \(x\) 和 \(y\) 不同，那么 \(\mathrm{Number}(x)-\mathrm{Number}(y)\) 是一个非零整数。若它们在模 \(p\) 下指纹相等，则有：
\[\mathrm{Number}(x) \equiv \mathrm{Number}(y) \pmod p \]
也就是：
\[p \mid \left(\mathrm{Number}(x)-\mathrm{Number}(y)\right) \]
所以，错误只会发生在随机选中的 \(p\) 刚好是这个差值的某个素因子时。一个非零整数的素因子数量有限，而可选素数集合可以通过扩大范围来增加。
于是，只要 \(p\) 的可选范围越大，坏素数所占比例就会越低。这就是模素数指纹法的基本逻辑：不是保证没有碰撞，而是让碰撞需要满足一个很具体、很稀疏的条件。
考虑一个通信问题。机器 RI 有一个字符串 \(x \in \{0,1\}^n\)，机器 RII 有一个集合 \(U=\{u_1,u_2,\ldots,u_k\}\)，其中每个 \(u_i\) 也是长度为 \(n\) 的二进制串。RI 不知道 \(U\)，RII 不知道 \(x\)，它们要判断 \(x \in U\)。
最直接的方法是 RI 把整个 \(x\) 发过去，通信量是 \(n\) bit。随机指纹法可以把通信量降到 \(O(\log n)\)，代价是引入单边错误。
RI:
choose random prime p from PRIME(n^2)
s = Number(x) mod p
send (p, s) to RII
RII:
for each u_i in U:
q_i = Number(u_i) mod p
if s is equal to some q_i:
output "x may be in U"
else:
output "x is not in U"
这里 \(\mathrm{PRIME}(n^2)\) 表示不超过 \(n^2\) 的素数集合。因为 \(p \le n^2\)，发送 \(p\) 需要约 \(2\log n\) bit；又因为 \(s < p\)，发送 \(s\) 也需要约 \(2\log n\) bit。所以总通信复杂度大约是 \(4\log n\)，也就是 \(O(\log n)\)。
这个协议的正确性方向很清楚。如果 \(x \in U\)，设 \(x=u_j\)，那么对任何 \(p\) 都有 \(\mathrm{Finger}_p(x)=\mathrm{Finger}_p(u_j)\)，协议一定会输出“在集合中”。
错误只可能发生在 \(x \notin U\) 时。此时某个 \(u_i\) 可能满足：
\[\mathrm{Number}(x) \equiv \mathrm{Number}(u_i) \pmod p \]
也就是一次碰撞。
在 \(\mathrm{PRIME}(n^2)\) 的质数选取范围下，错误的概率具体有多大呢？设 \(x\notin U\)。对每个 \(u_i\)，令
\[\Delta_i = \left|\mathrm{Number}(x)-\mathrm{Number}(u_i)\right| \]
因为 \(x\ne u_i\)，所以 \(\Delta_i\ne 0\)；又因为二者都是 \(n\) 位二进制串，所以 \(\Delta_i < 2^n\)。如果 \(x\) 和 \(u_i\) 在模 \(p\) 下发生碰撞，那么 \( p\mid \Delta_i \)。
而数论知识还告诉我们，一个小于 \(2^n\) 的非零整数最多有 \(n\) 个不同的素因子。所以，对一个固定的 \(u_i\)，能造成碰撞的坏素数最多有 \(n\) 个。对所有 \(k\) 个元素，坏素数总数最多有 \(kn\) 个。
另一方面，不超过 \(n^2\) 的素数个数约为
\[\pi(n^2) \sim \frac{n^2}{\ln(n^2)} = \frac{n^2}{2\ln n} \]
所以随机选中坏素数的概率最多约为
\[\frac{kn}{\pi(n^2)} \approx \frac{kn}{n^2/(2\ln n)} = \frac{2k\ln n}{n} \]
这符合直觉：元素数量 \(k\) 越多，越容易冲突；而当质数范围取 \(n^2\) 时，规模越大越不容易冲突。当
\[k \le \frac{n}{4\ln n} \]
时，错误概率就至多约为 \(\frac 12\)。
为什么 \(\frac 12\) 这个节点这么重要呢？它重要是因为，一旦单次错误概率被压到某个小于 \(1\) 的常数，就可以通过独立重复把错误概率指数级压低。重复 \(t\) 轮，每一轮都重新选择独立的随机素数，并且只有每一轮都发生碰撞才会误判，那么错误概率最多变成：
\[2^{-t} \]
随着次数增加，错误概率会迅速降低；而只要问题规模较大，\(k\) 次实验发送的 \(4k\log n\) bit 仍然远小于 \(n\) 个全部比特。
这种协议叫 one-sided-error Monte Carlo protocol。它会很快给出答案，但答案只有一个方向是绝对可靠的：如果它说 \(x \notin U\)，那一定是真的；如果它说 \(x \in U\)，则可能是碰撞造成的假阳性。
上面可以问题可以推广。RI 有 \(V=\{v_1,v_2,\ldots,v_l\}\)，RII 有 \(U=\{u_1,u_2,\ldots,u_k\}\)，目标是判断 \(U \cap V\) 是否为空。
那么思路仍然没有变化，RI 选择一个随机素数 \(p\)，计算自己每个元素的指纹并发送，RII 也计算自己每个元素的指纹，并和 RI 发送的指纹比较。直接发送整个集合需要 \(O(ln)\) bit。使用随机指纹时，RI 只需要发送一次 \(p\)，再发送 \(l\) 个元素的模 \(p\) 指纹，通信量变为 \(O(l\log n)\) bit。
如果 \(U \cap V \ne \emptyset\)，真实公共元素一定会产生相同指纹，所以不会漏报。若 \(U \cap V = \emptyset\)，协议可能因为某一对 \((u_i,v_j)\) 的碰撞而误报“有交集”。
这里的错误风险不再只和 \(k\) 有关，而是和 \(k \cdot l\) 有关，因为每一对元素都可能成为碰撞源。若 \(U\cap V=\emptyset\)，那么每一对 \((u_i,v_j)\) 都是不相等的。对固定一对元素，碰撞要求：
\[p\mid \left(\mathrm{Number}(u_i)-\mathrm{Number}(v_j)\right) \]
这个非零差值仍然小于 \(2^n\)，所以最多有 \(n\) 个不同素因子可能造成碰撞。
现在这样的元素对一共有 \(kl\) 个，因此所有可能导致误报的坏素数总数最多是 \(kln\)。随机从 \(\mathrm{PRIME}(n^2)\) 中选 \(p\)，错误概率最多约为：
\[\frac{kln}{\pi(n^2)} \approx \frac{2kl\ln n}{n} \]
因此，只要
\[|U| \cdot |V| = o\left(\frac{n}{\ln n}\right) \]
错误概率就会随着 \(n\) 增大而趋近于 \(0\)。如果希望把单次错误概率压到大约不超过 \(1/2\)，可以要求：
\[|U| \cdot |V| \le \frac{n}{4\ln n} \]
在对象对数太多时，碰撞机会会累积。想继续压低错误概率，要么增加指纹长度，要么重复多轮独立随机试验。这里体现的是一个非常常见的原则：单个比较的碰撞概率再低，也会被大量比较通过 union bound 放大。
上面的协议是 Monte Carlo 型的：它运行很快，但在某个方向上允许小概率错误。另一种常见改造是 Las Vegas 型：先用随机指纹做便宜的初筛，如果指纹已经不同，就直接给出确定的否定答案；如果指纹相同，则回到原对象上做一次完整验证。
这样一来，算法不再出错。因为所有可能出错的“指纹相同”情形，都会被后续的完整验证拦住。
可以把期望成本写成一个简单公式。设随机指纹阶段的成本为 \(T_f\)，完整验证的成本为 \(T_v\)，假阳性概率为 \(\varepsilon\)。在真实答案是否定的情况下，只有发生碰撞时才会进入完整验证，所以期望成本为：
\[T_f+\varepsilon T_v \]
例如成员判断中，如果 \(x\notin U\)，初筛大多数时候会直接发现“不在集合中”。只有当 \(x\) 和某个 \(u_i\) 的指纹碰撞时，才需要让 RI 发送完整的 \(x\)，或者用其他确定性方式检查。因此期望通信量可以写成：
\[O(\log n)+\varepsilon O(n) \]
如果通过扩大素数范围或重复独立试验把 \(\varepsilon\) 压得足够低，那么第二项就会变小。
但 Las Vegas 改造并不是免费午餐。在真实答案是肯定的情况占多数下，例如 \(x\in U\)，真实相等的元素必然产生相同指纹，于是不管如果选取质数，完整验证通常一定会发生。这样也就退化成了全部比较。
Monte Carlo 用小概率错误换取始终很快；Las Vegas 消除了错误，但把部分情形的完整成本放进了期望复杂度里。适合哪一种，取决于应用更不能接受错误，还是更不能接受偶尔变慢。
再看一个例子。给定三个 \(n\times n\) 矩阵 \(A,B,C\)，要判断 \(A\cdot B=C\)。如果直接计算 \(A\cdot B\) 需要 \(O(n^3)\) 时间。而 Freivalds 算法把验证降到了 \(O(n^2)\)。
随机选择一个向量 \(\alpha \in \{0,1\}^n\)，然后计算：
\[\beta = A\cdot(B\cdot \alpha), \qquad \gamma = C\cdot \alpha \]
如果 \(\beta \ne \gamma\)，输出 \(A\cdot B \ne C\)；如果 \(\beta=\gamma\)，接受 \(A\cdot B=C\)，或者说认为它们“可能相等”。
这里就利用了“不计算，只验证”的思想。直接计算 \(A\cdot B\) 是复杂的。但是，矩阵乘向量只需要 \(O(n^2)\)，所以 \(B\cdot \alpha\)、\(A\cdot(B\cdot\alpha)\) 和 \(C\cdot\alpha\) 都只需要 \(O(n^2)\)。整个过程不需要显式算出完整的 \(A\cdot B\)。
如果 \(A\cdot B=C\)。那么对任何 \(\alpha\) 都有 \(A\cdot B\cdot\alpha=C\cdot\alpha\)，算法不会误判为不相等。
若 \(A\cdot B \ne C\)。令 \(D=A\cdot B-C\)，则 \(D\ne 0\)。我们希望随机选出的 \(\alpha\) 让 \(D\alpha \ne 0\)。
为什么至少一半的 \(\alpha\) 能发现错误？因为 \(D\) 至少有一行非零，记为 \(d=(d_1,\ldots,d_n)\)。存在某个 \(d_j\ne 0\)。固定 \(\alpha\) 中除 \(\alpha_j\) 外的其他坐标后，表达式 \(d\cdot\alpha\) 可以看作关于 \(\alpha_j\) 的一次式：
\[d_j\alpha_j + c \]
其中 \(c\) 由其他坐标决定。由于 \(d_j \ne 0\)，在 \(\alpha_j \in {0,1}\) 的两个选择中，不可能两个都让它等于 \(0\)。如果 \(c=0\)，那么 \(\alpha_j=1\) 时值为 \(d_j\ne 0\)；如果 \(c\ne 0\)，也至多只有一个选择会把它抵消为 \(0\)。
于是，在所有 \(2^n\) 个 0-1 向量中，至少 \(2^{n-1}\) 个能让这一行的内积非零，从而让 \(D\alpha\ne 0\)。
所以，一次运行的错误概率最多是 \(1/2\)。独立重复 \(t\) 次，并且只有每次都通过才接受 \(A\cdot B=C\)，错误概率最多降为 \(2^{-t}\)，复杂度变为 \(O(tn^2)\)。当 \(t\) 是几十这样的常数时，这在工程上已经非常强。
这个算法的美感在于，它并没有计算要验证的对象本身，而是随机观察它在某个方向上的投影。若两个矩阵真的不同，它们在至少一半的 0-1 方向上会表现出差异。
很多看似不同的算法，都在使用同一个原则：不直接比较对象本身，而是比较它们在某个随机选择下的影子。
要在长文本 \(T\) 中寻找模式串 \(P\)，朴素方法会把 \(P\) 和 \(T\) 的每个等长窗口逐字符比较。Rabin-Karp 则先比较窗口的指纹。
如果指纹不同，窗口一定不匹配；如果指纹相同，再逐字符确认。由于相邻窗口只差一个字符，指纹还可以滚动更新，不必每次从头计算。这就是随机指纹在字符串算法中的典型用法：它不直接证明两个字符串相等，而是快速排除大量“不可能相等”的候选。
给定两个多项式 \(P(x)\) 和 \(Q(x)\)，要判断它们是否完全相同。直接展开可能很贵，但可以随机选一个点 \(r\)，比较：
\[P(r) \quad \text{和} \quad Q(r) \]
如果 \(P=Q\)，那么对所有 \(r\) 都相等。若 \(P\ne Q\)，则 \(P-Q\) 是一个非零多项式。一个次数为 \(d\) 的非零多项式最多只有 \(d\) 个根。因此，只要随机点来自足够大的集合，误判概率就不高。
集合也可以被编码成多项式。给定集合 \(S={s_1,\ldots,s_m}\)，定义：
\[P_S(z)=\prod_{i=1}^m(z-s_i) \]
如果两个集合 \(S\) 和 \(T\) 相等，那么 \(P_S=P_T\)。如果集合不同，则两个多项式不同。随机选择一个点 \(r\)，比较 \(P_S(r)\) 和 \(P_T(r)\)，就能用一个短值随机验证两个集合是否相等。
这些例子的共同点是：对象不同的时候，能让它们“看起来相同”的随机选择只占少数。随机性不是为了制造不确定，而是为了把潜在碰撞压缩到一个可计算、可放大的概率界里。
随机指纹适合“否定容易、肯定昂贵”的场景。两个指纹不同，通常可以立刻否定；两个指纹相同，则要看算法类型决定是否接受。成员判断和矩阵验证中的协议选择接受小概率错误，因此是 Monte Carlo；如果指纹相同后回查原文，就变成 Las Vegas。
它不适合无条件要求零错误、且又不能回查原对象的场景。比如安全认证里不能把普通随机哈希当作密码学承诺；面对主动攻击者时，也不能只靠短指纹断言两个对象完全相同。这里讨论的是算法意义上的随机化验证，不是密码学安全。
实现层面还有几个现实细节。随机源要足够独立，否则重复试验未必能按 \(2^{-t}\) 衰减；模运算要注意溢出和负数；当对象数量很大时，单个碰撞概率再小也会被 union bound 放大。很多“理论上概率很低”的事件，在海量系统里会变成迟早发生的事件。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。