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?
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 &lt; \log{n}$ by using the hash function $((x \bmod{u})\bmod{v})$ where $u &lt; 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.