MMH* with arbitrary modulus is always almost-universal

Abstract

Universal hash functions, discovered by Carter and Wegman in 1979, are of great importance in computer science with many applications. MMH${}^{\ast }$ is a well-known $△$-universal hash function family, based on the evaluation of a dot product modulo a prime. In this paper, we introduce a generalization of MMH${}^{\ast }$, that we call GMMH${}^{\ast }$, using the same construction as MMH${}^{\ast }$ but with an arbitrary integer modulus $n>1$, and show that GMMH${}^{\ast }$ is $\frac{1}{p}$-almost-$△$-universal, where $p$ is the smallest prime divisor of $n$. This bound is tight.