# Is there any time efficient way of achieving the result of FKS hashing lemma?

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?

• 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? – D.W. Mar 23 '18 at 1:01

## 1 Answer

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.