企业官网建设流程全解析

程序里经常会遇到一种看似朴素、实际很贵的问题：两个东西是不是一样？

它可能是两个字符串、两个文件、两个集合、一段文本里的子串，或者三个矩阵是否满足 A⋅B=CA⋅B=C。如果对象本身很大，尤其是在对象需要跨机器通信、被反复比较、以流式方式到达，或者比较结果只需要高概率可靠时，直接逐个字节比较往往不是最想要的方案。

随机指纹法处理的正是这类问题。它不试图完整保留对象，而是把对象映射成一个短得多的值，然后比较这些短值。这个短值可能丢失信息，所以它不是压缩意义上的可逆编码，而更像一个可快速比较的影子。

影子不能替代实体，但如果影子不同，实体一定不同；如果影子相同，实体也许相同，也许只是碰巧投在了同一个地方。随机性的作用，是让这种“碰巧”变得可控。

指纹与哈希

指纹和哈希函数有相似之处。设对象集合为 OO，我们从一组映射 HH 中随机选择一个函数 ff，然后用 f(O)f(O) 作为对象 OO 的指纹。对于两个对象 O1O1​ 和 O2O2​：

• 如果 O1=O2O1​=O2​，那么必然有 f(O1)=f(O2)f(O1​)=f(O2​)；
• 如果 O1≠O2O1​=O2​，那么大多数 f∈Hf∈H 都能让 f(O1)≠f(O2)f(O1​)=f(O2​)。

第二点是关键。对于输出空间远小于输入空间的固定哈希函数，理论上总会存在碰撞；在非密码学场景下，如果对手知道函数，也可能针对性地寻找碰撞。随机选择函数后，对手很难提前知道我们会拿哪一把尺子去量对象。随机化并不是为了神秘，而是为了把最坏情况变成概率问题。

在算法分析里，能区分 O1O1​ 和 O2O2​ 的函数常被称为 witness，也就是“见证者”。如果某个 h∈Hh∈H 满足 h(O1)≠h(O2)h(O1​)=h(O2​)，那么 hh 就见证了 O1≠O2O1​=O2​。指纹法的设计目标，就是让见证者足够多，同时让每个指纹足够短。

这两个目标天然冲突。指纹越短，比较越快，通信越省，但碰撞空间也更大；指纹越长，错误概率更低，却离“直接发送原对象”越来越近。许多随机化算法的味道，就藏在这个 trade-off 里。

用随机素数给二进制串取指纹

一切复杂对象都可以映射成二进制数，而一切二进制串又可以看成整数。给定 x∈{0,1}nx∈{0,1}n，令 Number(x)Number(x) 表示它对应的二进制整数。例如 1011210112​ 对应十进制的 1111。

随机选择一个素数 pp，定义：

Fingerp(x)=Number(x)modpFingerp​(x)=Number(x)modp

这个定义非常朴素，但足够有力。如果有 xx 和 yy 不同，那么 Number(x)−Number(y)Number(x)−Number(y) 是一个非零整数。若它们在模 pp 下指纹相等，则有：

Number(x)≡Number(y)(modp)Number(x)≡Number(y)(modp)

也就是：

p∣(Number(x)−Number(y))p∣(Number(x)−Number(y))

所以，错误只会发生在随机选中的 pp 刚好是这个差值的某个素因子时。一个非零整数的素因子数量有限，而可选素数集合可以通过扩大范围来增加。

于是，只要 pp 的可选范围越大，坏素数所占比例就会越低。这就是模素数指纹法的基本逻辑：不是保证没有碰撞，而是让碰撞需要满足一个很具体、很稀疏的条件。

相等判断

考虑一个通信问题。机器 RI 有一个字符串 x∈{0,1}nx∈{0,1}n，机器 RII 有一个集合 U={u1,u2,…,uk}U={u1​,u2​,…,uk​}，其中每个 uiui​ 也是长度为 nn 的二进制串。RI 不知道 UU，RII 不知道 xx，它们要判断 x∈Ux∈U。

最直接的方法是 RI 把整个 xx 发过去，通信量是 nn bit。随机指纹法可以把通信量降到 O(log⁡n)O(logn)，代价是引入单边错误。

这里 PRIME(n2)PRIME(n2) 表示不超过 n2n2 的素数集合。因为 p≤n2p≤n2，发送 pp 需要约 2log⁡n2logn bit；又因为 s<ps<p，发送 ss 也需要约 2log⁡n2logn bit。所以总通信复杂度大约是 4log⁡n4logn，也就是 O(log⁡n)O(logn)。

这个协议的正确性方向很清楚。如果 x∈Ux∈U，设 x=ujx=uj​，那么对任何 pp 都有 Fingerp(x)=Fingerp(uj)Fingerp​(x)=Fingerp​(uj​)，协议一定会输出“在集合中”。

错误只可能发生在 x∉Ux∈/U 时。此时某个 uiui​ 可能满足：

Number(x)≡Number(ui)(modp)Number(x)≡Number(ui​)(modp)

也就是一次碰撞。

在 PRIME(n2)PRIME(n2) 的质数选取范围下，错误的概率具体有多大呢？设 x∉Ux∈/U。对每个 uiui​，令

Δi=∣Number(x)−Number(ui)∣Δi​=∣Number(x)−Number(ui​)∣

因为 x≠uix=ui​，所以 Δi≠0Δi​=0；又因为二者都是 nn 位二进制串，所以 Δi<2nΔi​<2n。如果 xx 和 uiui​ 在模 pp 下发生碰撞，那么 p∣Δip∣Δi​。

而数论知识还告诉我们，一个小于 2n2n 的非零整数最多有 nn 个不同的素因子。所以，对一个固定的 uiui​，能造成碰撞的坏素数最多有 nn 个。对所有 kk 个元素，坏素数总数最多有 knkn 个。

另一方面，不超过 n2n2 的素数个数约为

π(n2)∼n2ln⁡(n2)=n22ln⁡nπ(n2)∼ln(n2)n2​=2lnnn2​

所以随机选中坏素数的概率最多约为

knπ(n2)≈knn2/(2ln⁡n)=2kln⁡nnπ(n2)kn​≈n2/(2lnn)kn​=n2klnn​

这符合直觉：元素数量 kk 越多，越容易冲突；而当质数范围取 n2n2 时，规模越大越不容易冲突。当

k≤n4ln⁡nk≤4lnnn​

时，错误概率就至多约为 1221​。

为什么 1221​ 这个节点这么重要呢？它重要是因为，一旦单次错误概率被压到某个小于 11 的常数，就可以通过独立重复把错误概率指数级压低。重复 tt 轮，每一轮都重新选择独立的随机素数，并且只有每一轮都发生碰撞才会误判，那么错误概率最多变成：

2−t2−t

随着次数增加，错误概率会迅速降低；而只要问题规模较大，kk 次实验发送的 4klog⁡n4klogn bit 仍然远小于 nn 个全部比特。

这种协议叫 one-sided-error Monte Carlo protocol。它会很快给出答案，但答案只有一个方向是绝对可靠的：如果它说 x∉Ux∈/U，那一定是真的；如果它说 x∈Ux∈U，则可能是碰撞造成的假阳性。

集合不交：碰撞机会按成对数量累积

上面可以问题可以推广。RI 有 V={v1,v2,…,vl}V={v1​,v2​,…,vl​}，RII 有 U={u1,u2,…,uk}U={u1​,u2​,…,uk​}，目标是判断 U∩VU∩V 是否为空。

那么思路仍然没有变化，RI 选择一个随机素数 pp，计算自己每个元素的指纹并发送，RII 也计算自己每个元素的指纹，并和 RI 发送的指纹比较。直接发送整个集合需要 O(ln)O(ln) bit。使用随机指纹时，RI 只需要发送一次 pp，再发送 ll 个元素的模 pp 指纹，通信量变为 O(llog⁡n)O(llogn) bit。

如果 U∩V≠∅U∩V=∅，真实公共元素一定会产生相同指纹，所以不会漏报。若 U∩V=∅U∩V=∅，协议可能因为某一对 (ui,vj)(ui​,vj​) 的碰撞而误报“有交集”。

这里的错误风险不再只和 kk 有关，而是和 k⋅lk⋅l 有关，因为每一对元素都可能成为碰撞源。若 U∩V=∅U∩V=∅，那么每一对 (ui,vj)(ui​,vj​) 都是不相等的。对固定一对元素，碰撞要求：

p∣(Number(ui)−Number(vj))p∣(Number(ui​)−Number(vj​))

这个非零差值仍然小于 2n2n，所以最多有 nn 个不同素因子可能造成碰撞。

现在这样的元素对一共有 klkl 个，因此所有可能导致误报的坏素数总数最多是 klnkln。随机从 PRIME(n2)PRIME(n2) 中选 pp，错误概率最多约为：