FKS hashing lemma states.

Given a set of $n-$bit numbers $\{x_1,x_2,\dots,x_k\}$ there exist a prime $p$ of $O(\log n + \log k)$-bit such that $x_i$ mod $p \neq $ $x_j$ mod $p$ if $x_i \neq x_j$.

This follows from prime number theorem. But finding such a prime takes a lot of time. Are there more efficient hashing schemes which achieve the similar results?

  • 1
    $\begingroup$ Are you looking for deterministic algorithms or will you accept a randomized construction? What approaches have you considered? What constitutes a lot of time for you? $\endgroup$
    – D.W.
    Mar 23, 2018 at 1:01

1 Answer 1


DGS prove a hashing lemma that bijectively hashes a sparse set to a set from a smaller universe (without involving a primality test). In particular see Lemma 3 in the paper that maps a set of size at most $(\log n)^{1/3}$ from the universe $[n]$ to a set of size at most $v < \log{n}$ by using the hash function $((x \bmod{u})\bmod{v})$ where $u < n$.

I guess in your setting the set consists of elements from $n$-bit numbers and you can therefore plug in $2^n$ instead of $n$ in the DGS-lemma.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.