- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
Adler-32 校验和算法对 65521 求模求和。我知道 65521 是适合 16 位的最大质数,但为什么在此算法中使用质数很重要?
(我敢肯定,一旦有人告诉我答案就会显而易见,但我大脑中的数论部分无法正常工作。即使没有校验和算法方面的专业知识,阅读 http://en.wikipedia.org/wiki/Fletcher%27s_checksum 的聪明人也可能会给我解释一下。)
最佳答案
为什么 Adler32 使用 mod prime?
来自 Adler 自己的网站 http://zlib.net/zlib_tech.html
However, Adler-32has been constructed to minimize theways to make small changes in the datathat result in the same check value,through the use of sums significantlylarger than the bytes and by using aprime (65521) for the modulus. It isin this area that some analysis isdeserved, but it has not yet beendone.
The main reason for Adler-32 is, ofcourse, speed in softwareimplementations.
An alternative to Adler-32 is Fletcher-32, which replaces the modulo of 65521 with 65535. This paper shows that Fletcher-32 is superior for channels with low-rate random bit errors.
使用它是因为质数往往具有更好的混合特性。它到底有多好还有待讨论。
其他说明
这个线程中的其他人提出了一个有点令人信服的论点,即模数素数更适合检测位交换。然而,这很可能不是这种情况,因为位交换极为罕见。两个最普遍的错误是:
大多数位交换是由随机位翻转引起的,这些位翻转恰好看起来像位交换。
纠错码实际上是为了承受 n 位偏差而设计的。来自阿德勒的网站:
A properly constructed CRC-n has thenice property that less than n bits inerror is always detectable. This isnot always true for Adler-32--it candetect all one- or two-byte errors butcan miss some three-byte errors.
使用质数模数的效果
我就本质上相同的问题写了一篇很长的文章。为什么要对质数取模?
http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth
简短的回答
与合数相比,我们对素数的了解要少得多。因此像 Knuth 这样的人开始使用它们。
虽然素数与我们散列的大部分数据关系不大,但增加表/模数大小也会降低冲突的可能性(有时比四舍五入到最接近的素数所获得的任何好处都多)。
这是一个graph比较 mod 65521 与 65535 的每个桶与 1000 万个加密随机整数的碰撞次数。
关于algorithm - 为什么在 Adler-32 校验和算法中对 65521 取模?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/927277/
我有以下情况:一个包含大文件的目录树(大约 5000 个文件,大小约为 4Gb)。我需要在这棵树中查找重复项。 我尝试使用 Java 内置的 CRC32 和 Adler32 类,但它非常慢(每个文件大
我目前正在编写一个 C 程序,该程序从另一个生成的数据文件构建 PNG 图像。图像是调色板类型。 Adler-32 校验和是针对...的未压缩数据计算的吗 a) IDAT 数据 block 中的每个压
Adler-32 校验和算法对 65521 求模求和。我知道 65521 是适合 16 位的最大质数,但为什么在此算法中使用质数很重要? (我敢肯定,一旦有人告诉我答案就会显而易见,但我大脑中的数论部
CRC-32 有一个奇妙的特性,即在消息末尾附加一个 CRC 允许您通过计算整个事物的 CRC 来执行消息验证,如果校验和通过,则最终结果将为零。 这个属性应该适用于 CRC-32 的兄弟 Adler
我遇到了一些 zlib 压缩的不同实现之间不兼容的问题。 作为测试用例,我想创建具有 10000 个 double 的测试数据,范围从 0 到 10000。 我创建了一些测试代码来压缩和解压缩此数据,
我是一名优秀的程序员,十分优秀!