Adler-32 校验和算法以 65521 为模求和。我知道 65521 是适合 16 位的最大素数，但为什么在该算法中使用素数很重要？
（我敢肯定，一旦有人告诉我，答案似乎很明显，但我大脑中的数论部分无法正常工作。即使没有校验和算法方面的专业知识，也是一个阅读http://en.wikipedia的聪明人。 org/wiki/Fletcher%27s_checksum可能可以向我解释。）
问问题
5331 次
6 回答
20
为什么 Adler32 使用 mod prime？
来自 Adler 自己的网站http://zlib.net/zlib_tech.html
然而，Adler-32 已被构建为通过使用显着大于字节的总和以及使用素数 (65521) 作为模数，最大限度地减少对数据进行微小更改而导致相同校验值的方法。正是在这方面，值得进行一些分析，但尚未完成。
Adler-32 的主要原因当然是软件实现的速度。
Adler-32 的替代方案是 Fletcher-32，它将 65521 的模替换为 65535。本文表明 Fletcher-32 对于低速率随机误码的信道具有优势。
使用它是因为素数往往具有更好的混合特性。到底有多好还有待商榷。
其他说明
该线程中的其他人提出了一个有些令人信服的论点，即模数素数更适合检测位交换。但是，这很可能不是这种情况，因为位交换极为罕见。两个最普遍的错误是：
- 随处可见的随机位翻转 (1 <-> 0)。
- 网络中常见的位移（1 2 3 4 5 -> 2 3 4 5 或 1 1 2 3 4 5）
那里的大多数位交换是由碰巧看起来像位交换的随机位翻转引起的。
事实上，纠错码被设计成能承受 n 位的偏差。来自阿德勒的网站：
正确构造的 CRC-n 具有很好的特性，即始终可以检测到少于 n 位的错误。Adler-32 并非总是如此——它可以检测到所有一字节或两字节错误，但可能会漏掉一些三字节错误。
使用素数模数的有效性
我对基本相同的问题做了很长的文章。为什么要对素数取模？
http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth
简短的回答
我们对素数的了解远少于合数。因此，像 Knuth 这样的人开始使用它们。
虽然素数与我们散列的大部分数据的关系可能确实较少，但增加表/模大小也会降低冲突的可能性（有时比四舍五入到最接近的素数所获得的任何好处都多）。
于 2009-06-09T02:52:29.287 回答
4
Adler-32 算法是计算
A = 1 + b1 + b2 + b3 + ...
和
B = (1 + b1) + (1 + b1 + b2) + (1 + b1 + b2 + b3) + ... = 1 + b1 + 2 * b2 + 3 * b3 + ...
并以 m 为模报告它们。当 m 是素数时，以 m 为模的数字形成数学家所说的域。域有一个方便的性质，即对于任何非零 c，我们有 a = b 当且仅当 c * a = c * b。比较时间表模 6（不是素数）与时间表模 5（即：
* 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1
* 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
现在，每当我们交换两个字节时，A 部分就会被愚弄——加法毕竟是可交换的。B 部分应该检测这种错误，但是当 m 不是素数时，更多的位置容易受到攻击。考虑一个 Adler 校验和 mod 6
1 3 2 0 0 4
我们有 A = 4 和 B = 1。现在考虑交换 b2 和 b4：
1 0 2 3 0 4
A 和 B 不变，因为 2 * 3 = 4 * 0 = 2 * 0 = 4 * 3（模 6）。也可以将 2 和 5 交换为相同的效果。这更有可能在时间表不平衡时（模 5）检测到这些变化。事实上，唯一一次质数模数无法检测到单个交换是两个相等的索引 mod m 交换时（如果 m 很大，它们必须相距很远！）。^ 这个逻辑也可以应用于交换的子字符串。
使用较小模数的缺点是它在随机数据上失败的频率会稍高一些；然而，在现实世界中，腐败很少是随机的。
^ 证明：假设我们用值 a 和 b 交换索引 i 和 j。那么 a i + b j = a j + b i，所以 a i - a j + b j - b i = 0 且 (a - b)*(i - j) = 0。由于域是一个积分域，它遵循 a = b（值是全等的）或 i = j（索引是全等的）。
编辑：Unknown 链接到的网站 ( http://www.zlib.net/zlib_tech.html ) 清楚地表明 Adler-32 的设计根本没有原则。由于 DEFLATE 流中的 Huffman 代码，即使是小的错误也可能会改变帧（因为它依赖于数据）并导致输出中的大错误。考虑这个答案是一个稍微人为的例子，说明为什么人们将某些属性归因于素数。
于 2009-06-09T03:39:57.783 回答
3
长话短说：
素数的模具有最好的位混洗特性，这正是我们想要的哈希值。
于 2009-05-29T18:42:17.277 回答
1
对于完全随机的数据，桶越多越好。
假设数据在某种程度上是非随机的。现在，非随机性可能影响算法的唯一方法是创建一种情况，即某些存储桶比其他存储桶被使用的概率更高。
如果模数不是素数，则影响构成模数之一的任何模式都可能影响散列。因此，如果您使用 15，则每 3 或 5 次以及每 15 次的模式可能会导致冲突，而如果您使用 13，则模式必须每 13 次才会导致冲突。
65535 = 3*5*17*257，因此涉及 3 或 5 的模式可能会使用此模数导致冲突——例如，如果由于某种原因 3 的倍数更常见，那么只有 3 的倍数的桶才会善用。
现在我不确定这是否真的会成为一个问题。使用想要散列的类型的实际数据而不是随机数凭经验确定冲突率会很好。（例如，涉及 http://en.wikipedia.org/wiki/Benford's_law">本福德定律或某些此类不规则性的数值数据是否会导致影响该算法的模式？如何将 ASCII 代码用于现实文本？）
于 2009-06-09T19:13:13.477 回答
0
校验和通常用于检测两件事不同，尤其是在两件事在同一时间和地点不可用的情况下。它们可能在不同的地方可用（例如，发送的信息包与接收的信息包）或不同的时间（例如，存储时的信息块，与回读时的信息块） . 在某些情况下，可能需要检查两个独立存储在两个不同位置的东西是否可能匹配，而不必将实际数据从一个设备发送到另一个设备（例如比较加载的代码图像或配置）。
如果被比较的事物不匹配的唯一原因是其中之一的随机损坏，那么对 Adler-32 校验和使用素数模数可能不是特别有用。但是，如果其中一件事可能对其进行了一些“故意”更改，则使用非素数模数可能会导致某些更改被忽视。例如，将一个字节从 00 更改为 FF，并将另一个早于或晚于 257 个字节的倍数的另一个字节从 FF 更改为 00，在使用 Fletcher 校验和时会抵消，但在使用 Adler-32 校验和时不会。随机损坏不太可能发生这种情况，但是在更改程序时可能会发生这种抵消变化。他们不太可能
于 2011-08-26T17:32:23.333 回答
0
答案在于场论。具有运算加和时间的集合 Z/Z_n 是当 n 是素数时的字段（即，模数为 n 的加法和乘法）。
换句话说，以下等式：
m * x = (in Z/Z_n)
对于 m 的任何值（即 x = 0）只有一个解
考虑这个例子：
2 * x = 0 (mod 10)
这个方程有两个解，x = 0 和 x = 5。那是因为 10 不是素数，可以写成 2 * 5。
此属性负责更好地分布散列值。
于 2013-11-26T08:00:21.673 回答