Why modulo 65521 in Adler-32 checksum algorithm?
Long story short:
The modulo of a prime has the best bit-shuffeling properties, and that's exactly what we want for a hash-value.
The Adler-32 algorithm is to compute
A = 1 + b1 + b2 + b3 + ...
and
B = (1 + b1) + (1 + b1 + b2) + (1 + b1 + b2 + b3) + ... = 1 + b1 + 2 * b2 + 3 * b3 + ...
and report them modulo m. When m is prime, the numbers modulo m form what mathematicians call a field. Fields have the handy property that for any nonzero c, we have a = b if and only if c * a = c * b. Compare the times table modulo 6, which is not a prime, with the times table modulo 5, which is:
* 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
Now, the A part gets fooled whenever we interchange two bytes -- addition is commutative after all. The B part is supposed to detect this kind of error, but when m is not a prime, more locations are vulnerable. Consider an Adler checksum mod 6 of
1 3 2 0 0 4
We have A = 4 and B = 1. Now consider swapping b2 and b4:
1 0 2 3 0 4
A and B are unchanged because 2 * 3 = 4 * 0 = 2 * 0 = 4 * 3 (modulo 6). One can also swap 2 and 5 to the same effect. This is more likely when the times table is unbalanced -- modulo 5, these changes are detected. In fact, the only time a prime modulus fails to detect a single swap is when two equal indexes mod m are swapped (and if m is big, they must be far apart!).^ This logic can also be applied to interchanged substrings.
The disadvantage in using a smaller modulus is that it will fail slightly more often on random data; in the real world, however, corruption is rarely random.
^ Proof: suppose that we swap indexes i and j with values a and b. Then ai + bj = aj + bi, so ai - aj + bj - bi = 0 and (a - b)*(i - j) = 0. Since a field is an integral domain, it follows that a = b (values are congruent) or i = j (indexes are congruent).
EDIT: the website that Unknown linked to (http://www.zlib.net/zlib_tech.html) makes it clear that the design of Adler-32 was not at all principled. Because of the Huffman code in a DEFLATE stream, even small errors are likely to change the framing (because it's data-dependent) and cause large errors in the output. Consider this answer a slightly contrived example for why people ascribe certain properties to primes.
Why was mod prime used for Adler32?
From Adler's own website http://zlib.net/zlib_tech.html
However, Adler-32 has been constructed to minimize the ways to make small changes in the data that result in the same check value, through the use of sums significantly larger than the bytes and by using a prime (65521) for the modulus. It is in this area that some analysis is deserved, but it has not yet been done.
The main reason for Adler-32 is, of course, speed in software implementations.
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.
It was used because primes tend to have better mixing properties. Exactly how good it is remains to be discussed.
Other Explanations
Someone else in this thread makes a somewhat convincing argument that modulus a prime is better for detecting bit-swapping. However, this is most likely not the case because bit-swapping is extremely rare. The two most prevalent errors are:
- Random bit-flips (1 <-> 0) common anywhere.
- Bit shifting (1 2 3 4 5 -> 2 3 4 5 or 1 1 2 3 4 5) common in networking
Most of the bit-swapping out there is caused by random bit-flips that happened to look like a bit swap.
Error correction codes are in fact, designed to withstand n-bits of deviation. From Adler's website:
A properly constructed CRC-n has the nice property that less than n bits in error is always detectable. This is not always true for Adler-32--it can detect all one- or two-byte errors but can miss some three-byte errors.
Effectiveness of using a prime modulus
I did a long writeup on essentially the same question. Why modulo a prime number?
http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth
The short answer
We know much less about prime numbers than composite ones. Therefore people like Knuth started using them.
While it might be true that primes have less relationship to much of the data we hash, increasing the table/modulo size also decreases the probability of a collision (sometimes more than any benefit gained from rounding down to the nearest prime).
Here is a graph of collisions per bucket with 10 million cryptographically random integers comparing mod 65521 vs 65535.