Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
