Because my explanation has so many words, I'll start with my question and then you can read the explanation if you need to:

The Bernstein Hash method uses the number 33 as a multiplier.  From what I've read Bernstein himself has no reasonable explanation as to why 33 has such useful properties.  I'm wondering if the mathematics community has any theories on the matter.



The explanation:

I'm a software engineer and I was recently working on a blog post about a hash function I was writing.  In the process of designing my hash function, I looked at a lot of implementations of other hash functions.

For non-programmers, the gist is that the hashcodes produced by objects should be well distributed throughout the range of values in a 32 bit integer (-2,147,483,648 through 2,147,483,647).

Let's say I have the string "ABCD."  A hash function would loop through each character, get the ASCII value of it, do something to it and aggregate it into a composite hashcode.

For example, in a lot of implementations, they'd take a hashcode initialized to a large prime, multiply it by another prime and the XOR it with the value of 'A' which is 65.  Then, they'd take that and multiply it by the same prime and XOR that with the value of 'B'.  They'd do this until the end of the string is reached.

I found a clever implementation in the Java framework code that loops over each item and effectively applies this: $i = ((i \ll 5) - i) \oplus j$.  I was confused at first until I worked out that $(i \ll 5) - i = 31i$.  For a computer, bit shifting is faster than multiplying so this is a clever way to multiply by a prime number.

So, I looked in Microsoft's .Net framework and I found that they do it a little differently.  They use $(i \ll 5) + i$ instead!  I couldn't figure out for the life of me why they used 33 instead of 31 because from what I understand multiplying by prime numbers is the foundation of many hashing and cryptographic functions.

I found out that this technique is called the Bernstein Hash and that Bernstein himself doesn't know why 33 produces such a good distribution of values as a multiplier in hashing functions.

There's a simple proof which doesn't use Sylow's theory.
Lemma. Let $G$ a finite group with $n$ elements. If for every $d \mid n$,  $\# \{x \in G \mid x^d = 1 \} \leq d$, then $G$ is cyclic.
If $G$ is a finite subgroup of the multiplicative group of a field, then $G$ satisfies the hypothesis because the polynomial $x^d - 1$ has $d$ roots at most.
Proof.  Fix $d \mid n$ and consider the set $G_d$ made up of elements of $G$ with order $d$. Suppose that $G_d \neq \varnothing$, so there exists $y \in G_d$; it is clear that $\langle y \rangle \subseteq \{ x \in G \mid x^d = 1 \}$. But the subgroup $\langle y \rangle$ has cardinality $d$, so from the hypothesis we have that $\langle y \rangle = \{ x \in G \mid x^d = 1 \}$. Therefore $G_d$ is the set of generators of the cyclic group $\langle y \rangle$ of order $d$, so $\# G_d  = \phi(d)$.
We have proved that $G_d$ is empty or has cardinality $\phi(d)$, for every $d \mid n$. So we have:
$$\begin{align}
n &= \# G\\
& = \sum_{d \mid n} \# G_d \\
&\leq \sum_{d \mid n} \phi(d) \\
&= n.
\end{align}$$
Therefore $\# G_d = \phi(d)$ for every $d \vert n$. In particular $G_n \neq \varnothing$. This proves that $G$ is cyclic. QED
