MMH* with arbitrary modulus is always almost-universal
This provides a more flexible hash function for applications in computer science, though it is an incremental extension of existing work.
The paper tackles the problem of generalizing the MMH* universal hash function to use an arbitrary integer modulus instead of a prime, showing that the resulting GMMH* function is almost-universal with a tight bound based on the smallest prime divisor of the modulus.
Universal hash functions, discovered by Carter and Wegman in 1979, are of great importance in computer science with many applications. MMH$^*$ is a well-known $\triangle$-universal hash function family, based on the evaluation of a dot product modulo a prime. In this paper, we introduce a generalization of MMH$^*$, that we call GMMH$^*$, using the same construction as MMH$^*$ but with an arbitrary integer modulus $n>1$, and show that GMMH$^*$ is $\frac{1}{p}$-almost-$\triangle$-universal, where $p$ is the smallest prime divisor of $n$. This bound is tight.