为什么在Adler-32校验和算法中模数为65521？

Question

Adler-32校验和算法总和模数为65521.我知道65521是最大的素数,适合16位,但为什么在这个算法中使用素数很重要？

(我确信一旦有人告诉我,答案就会显而易见,但我脑中的数论理论部分却无法正常工作.即使没有校验和算法方面的专业知识,一个聪明的人也会阅读http://en.wikipedia. org/wiki/Fletcher%27s_checksum可能会向我解释.)

Answer 1

为什么mod prime用于Adler32？

来自Adler自己的网站http://zlib.net/zlib_tech.html

然而,Adler-32的构造是通过使用明显大于字节的和并使用模数的素数(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位偏差.来自Adler的网站:

正确构造的CRC-n具有良好的特性,即总是可以检测到小于n位的错误.对于Adler-32而言,情况并非总是如此 - 它可以检测所有单字节或双字节错误,但可能会错过一些三字节错误.

使用质数模量的有效性

我在基本相同的问题上做了很长的写作.为什么模数素数？

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

简短的回答

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

虽然素数与我们散列的大部分数据之间的关系可能较少,但增加表/模数也会降低碰撞的概率(有时甚至超过向下舍入到最接近的素数所获得的任何好处).

下面是每桶冲突的图表,其中有1000万个加密随机整数,比较mod 65521和65535.