Papers › The Power of Hashing with Mersenne Primes
The Power of Hashing with Mersenne Primes
Thomas Dybdahl Ahle, Jakob Tejs Bæk Knudsen, Mikkel Thorup
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The classic way of computing a k-universal hash function is to use a random degree-(k-1) polynomial over a prime field ℤₚ. For a fast computation of the polynomial, the prime p is often chosen as a Mersenne prime p=2ᵇ-1. In this paper, we show that there are other nice advantages to using Mersenne primes. Our view is that the hash function's output is a b-bit integer that is uniformly distributed in {0, …, 2ᵇ-1}, except that p (the all \texttt1s value in binary) is missing. Uniform bit strings have many nice properties, such as splitting into substrings which gives us two or more hash functions for the cost of one, while preserving strong theoretical qualities. We call this trick "Two for one" hashing, and we demonstrate it on 4-universal hashing in the classic Count Sketch algorithm for second-moment estimation. We also provide a new fast branch-free code for division and modulus with Mersenne primes. Contrasting our analytic work, this code generalizes to any Pseudo-Mersenne primes p=2ᵇ-c for small c.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections