为什么 Adler-32 校验和算法中要对 65521 求模？

Question

Adler-32 校验和算法对 65521 进行求和。我知道 65521 是适合 16 位的最大素数，但为什么在该算法中使用素数很重要？

（我确信一旦有人告诉我，答案就会显而易见，但我大脑的数论部分却不起作用。即使没有校验和算法方面的专业知识，聪明的人也会阅读 http://en.wikipedia.org/wiki/Fletcher%27s_checksum 也许可以向我解释一下。）

Answer 1

为什么 Adler32 使用 mod prime？

来自阿德勒自己的网站 http://zlib.net/zlib_tech.html

但是，已经构建了Adler-32，以最大程度地减少通过使用明显大于字节的总和和使用Prime（65521）的模量，从而最大程度地减少了导致相同检查值的微小变化的方法。 正是在这个领域，应该得到一些分析，但尚未进行。

当然，Adler-32的主要原因是软件实施的速度。

Adler-32 的替代方案是 Fletcher-32，它将 65521 的模替换为 65535。本文表明，Fletcher-32 对于具有低随机误码率的信道具有优越性。

使用它是因为底漆往往具有更好的混合性能。究竟有多好还有待讨论。

其他说明

该线程中的其他人提出了一个有点令人信服的论点，即模素数更适合检测位交换。然而，这最有可能是 事实并非如此 因为位交换极其罕见。两个最常见的错误是：

1. 随机位翻转 (1 <-> 0) 在任何地方都很常见。
2. 网络中常见的位移位（1 2 3 4 5 -> 2 3 4 5 或 1 1 2 3 4 5）

大多数位交换是由随机位翻转引起的，这些随机位翻转恰好看起来像位交换。

事实上，纠错码旨在承受 n 位偏差。来自阿德勒的网站：

正确构建的CRC-N具有一个不错的属性，即毫无疑问的错误始终可以检测到。对于Adler-32而言，这并不总是如此 - 它可以检测到所有一个或两个字节错误，但可能会错过一些三字节错误。

使用素数模的有效性

我就同一个问题写了一篇很长的文章。为什么要对素数取模？

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

简短的回答

我们对素数的了解远少于对合数的了解。因此，像 Knuth 这样的人开始使用它们。

虽然素数与我们散列的大部分数据的关系可能确实较小，但增加表/模大小也会降低冲突的概率（有时比向下舍入到最接近的素数所获得的好处更多）。

下面是每个桶与 1000 万个加密随机整数的碰撞图，比较了 mod 65521 和 65535。

Answer 2

在阿德勒-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

现在，每当我们交换两个字节的一部分被愚弄 - 加法是可交换的毕竟。在B部分应该检测这种错误，但是当m不是素，多个位置是脆弱的。考虑的阿德勒校验模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大，所以一定要相距甚远！）。^这个逻辑也适用于互换子。

在使用较小的弹性模量的缺点是，它会略微更经常失败上随机数据;在现实世界中，但是，腐败现象是很少随机的。

^证明：假设我们交换索引i和j与值a和b。然后一个我+ b的 J =一个Ĵ+ B I，所以 I - 一个 J + B'EM>Ĵ - B I = 0和（a - b）中*（I - j）的。= 0由于字段是一体的结构域，它遵循A = b（值是全等）或I = j的（索引是全等）

编辑：该未知连接于（ http://www.zlib.net/zlib_tech该网站。 HTML ）清楚地表明，阿德勒-32的设计是不是在所有原则性。因为在DEFLATE流霍夫曼码，即使是小错误都可能改变取景（因为它是数据依赖型）和产生较大的误差输出。考虑这一点回答人们为什么归咎于某些属性，以质数稍人为的例子。

Answer 3

长话短说：

素的模有最好的位shuffeling性能，而这正是我们想要的哈希值。

Answer 4

有关完全随机的数据，越桶越好。

让我们说的数据在某种程度上是不随机的。现在，非随机性会影响算法的唯一方法是通过创建一个情况：一些水桶比别人正在使用的概率较高。

如果模数是非素数，则影响构成模的号码中的一个的任何图案可能会影响所述散列。所以，如果你正在使用15，一个模式，每3或者5，以及每15可能导致冲突，而如果你使用13模式将不得不每13引起的碰撞。

65535 = 3 * 5 * 17 * 257，所以涉及3或5的图案可能会导致使用这种modulo--如果3的倍数是出于某种原因常见得多，例如，然后仅是倍数水桶碰撞3将被善加利用。

现在我不知道是否现实，这很可能是一个问题。这将是很好的一个要散列，而不是随机数类型的实际数据凭经验确定的碰撞率。 （例如，将数值数据涉及http://en.wikipedia.org/wiki/Benford's_law">Benford's法或一些这样的不规则图案的原因会影响这个算法？关于使用ASCII码为现实的文本怎么样？）

Answer 5

校验和通常使用的检测两件事情是不同的，尤其是在两件事不可用在同一时间和地点的情况下的意图。他们可能可以在不同的地方（例如，作为发送，对信息的数据包所收到的信息的数据包），或在不同时间（例如，当它被保存，对信息块，当它被读回的信息块） 。在一些情况下，可能期望检查独立地存储在两个不同的地方两件事情是否可能匹配，而无需从一个设备发送的实际数据传送到其他（例如比较加载的代码图象或配置）。

如果被比较的东西将不匹配。将它们中的一个的随机损坏的唯一原因，那么使用用于阿德勒-32校验一个质数模数的可能不是特别有帮助。但是，如果这是可能的事情之一可能有给它做了一些“故意”的变化，使用非主要模数可能会造成一定的变化被忽视。例如，改变从00字节到FF，以及改变另一个字节这257个字节的某个倍数的影响早于或晚从FF到00，将使用当弗莱彻的校验和，但不使用阿德勒-32校验和时抵消。这不是特别可能是这样的场景会从随机腐败发生，但改变一个程序时，可能会出现这样的偏置变化。这不会是特别容易，他们会出现相隔257个字节的整数倍，但它可以通过使用一个质数模数（提供避免风险，至少，字节的文件中的数小于模量）

Answer 6

答案就在该领域的理论。 集合Z / Z_n与运算加上UND倍是一个字段，当n是一个素数（即除了UND乘法用模n）。

在换句话说，下面的等式：

m * x = (in Z/Z_n) 

仅具有一个任何值OFM（即X = 0）

溶液

考虑这个例子：

2 * x = 0 (mod 10)

此方程有两个解中，x = 0和x = 5。这是因为10不是素数，可写为2 * 5。

此属性负责的哈希值的更好的分布。