<p><a href="https://www.sciencedirect.com/science/article/pii/S0019995886800067" rel="nofollow noreferrer">DGS</a> 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$.</p>

<p>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.</p>

CC BY-SA 3.0
2018-04-04T14:04:21.327Z
2018-04-04T14:04:21.327Z
SamiD
<p>FKS hashing lemma states.</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p>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?</p>

CC BY-SA 3.0
2018-03-23T01:01:47.907Z
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.
<cc.complexity-theory><ds.algorithms><nt.number-theory>
Is there any time efficient way of achieving the result of FKS hashing lemma?
Vimal Raj Sharma
# Is there any time efficient way of achieving the result of FKS hashing lemma?

(Asked by: username_0 on 2018-03-22)

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?

**Tags:** cc.complexity-theory, ds.algorithms, nt.number-theory

> **Comments:**
> **username_1**: 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?  

---

## 1 answers

### Answer by username_2 on 2018-04-04. Score: 1

[DGS](https://www.sciencedirect.com/science/article/pii/S0019995886800067) 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.


---

