为什么在Adler-32校验和算法中使用模65521?

为什么Adler32使用mod prime?

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

对数据进行微小更改的方法 通过使用总和 大于字节并使用 它是 在这方面,需要进行一些分析 完成。

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

其他解释

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

1. 任意位置常见的随机位翻转(1<->0)。
2. 网络中常见的位移位(12345->23445或123445)

大部分的位交换都是由随机的位翻转引起的,这些位翻转看起来就像是位交换。

正确构造的CRC-n具有 这是一个很好的属性,在 错误总是可以检测到的。这是 对于Adler-32来说并不总是如此——它可以 检测所有单字节或双字节错误,但 可能会丢失一些三字节错误。

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

简短的回答

虽然素数与我们散列的大部分数据的关系可能较小,但增加表/模大小也会降低冲突的概率(有时比舍入到最接近的素数所获得的任何好处都要大)。

这是一个 graph 每桶1000万个加密随机整数的冲突数,比较mod 65521和65535。

A = 1 + b1 + b2 + b3 + ...

和

B = (1 + b1) + (1 + b1 + b2) + (1 + b1 + b2 + b3) + ... = 1 + b1 + 2 * b2 + 3 * b3 + ...

并以m的模报告它们。当m是素数时,模m的数就形成了数学家所说的a 领域 . 字段有一个便利的属性,即对于任何非零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

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交换。然后 i+b j+b i、 那么 i-a j+b

编辑:链接到的未知网站( http://www.zlib.net/zlib_tech.html

长话短说:

素数的模具有最好的位剥离特性,这正是我们想要的哈希值。

如果模数是非素数,那么任何影响构成模的数字之一的模式都可能影响哈希。因此,如果使用15,则每3或5个模式以及每15个模式都可能导致碰撞,而如果使用13,则必须每13个模式才能导致碰撞。

65535=3*5*17*257,所以一个包含3或5的模式可能会使用这个模引起冲突——例如,如果由于某种原因,3的倍数更为常见,那么只有3的倍数的桶才能被很好地使用。

现在,我不确定,实际上,这是否可能成为一个问题。最好是根据经验确定碰撞率,而不是随机数,而使用要散列的类型的实际数据。(例如,数字数据是否涉及http://en.wikipedia.org/wiki/Benford“s_定律”>本福德定律或某些类似的不规则性会导致影响此算法的模式?对真实文本使用ASCII码如何?)

校验和通常用于检测两个事物是否不同,特别是在两个事物不能同时在同一时间和地点使用的情况下。它们可能在不同的位置(例如,发送的信息包与接收的信息包)或不同的时间(例如,存储的信息块与读回的信息块)可用。在某些情况下,可能需要检查独立存储在两个不同位置的两件物品是否可能匹配,而不必将实际数据从一个设备发送到另一个设备(例如,比较加载的代码图像或配置)。

如果被比较的对象不匹配的唯一原因是其中一个对象的随机损坏,那么对Adler-32校验和使用素数模可能没有特别大的帮助。然而,如果其中一件事情可能有一些“故意”的改变,使用非素数模可能会导致某些改变不被注意。例如,当使用Fletcher校验和时,将一个字节从00更改为FF,并将另一个字节(先前或之后为257字节的倍数)从FF更改为00的效果将被抵消,但在使用Adler-32校验和时则不会。这种情况不太可能因随机损坏而发生,但在更改程序时可能会发生这种抵消更改。它们不太可能以257字节的精确倍数出现,但这是一种风险,可以通过使用素数模来避免(至少,如果文件中的字节数小于模数)

答案在于场论。 当n是素数(即模n的加法和乘法)时,具有运算加und次的集合Z/Z_n是一个字段。

m * x = (in Z/Z_n) 

考虑这个例子:

2 * x = 0 (mod 10)

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

此属性负责更好地分配哈希值。