Prove fingerprinting

Question

Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that $$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c \ln(n)/(n^{c-1}).$$

Hint: As a consequence of the prime number theorem, exactly $n/ \ln(n) \pm o(n/\ln(n))$ many numbers from $\{ 1, \ldots, n \}$ are prime.

Conclusion: we can compress $n$ bits to $O(\log(n))$ bits and get a quite small false-positive rate.

My question is how can i proove that $$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c \ln(n)/(n^{c-1})$$?

Answer 1

The probability $P$ that a uniformly chosen random prime between $1$ and $n^c$ satisfies $a \equiv b \mod{p}$ is the number of primes in this range that satisfy $a \equiv b \mod{p}$ divided by the total number of primes in this range. Writing $[C] = 1$ if $C$ is true and $[C] = 0$ if $C$ is false, and $\pi(x)$ for the number of primes less than $x$: $$P = \dfrac{\sum\limits_{p\le n^c} [p\text{ prime}] [p \mid (a-b)]}{\pi(n^c)}$$

Since $|a-b| \le 2^n$, there are at most $n$ distinct primes that divide $a-b$. The prime number theorem directly gives an upper bound for the denominator. Thus: $$ P \le \dfrac{n}{n^c/\ln(n^c) + o(n^c/\ln(n^c))} = \dfrac{c \ln(n)}{n^{c-1}} (1+o(1))$$

You won't get an exact bound from an asymptotic version of the prime number theorem. An exact bound, if I am not mistaken, is $\pi(x) \gt \dfrac{x}{\ln(x)}$ for $x \ge 11$. Using this bound, we see that if $n^c \ge 11$ then $$ P \le \dfrac{c \ln(n)}{n^{c-1}} $$

Application: we can compress $a \le 2^n$ (which takes $n$ bits to represent exactly) approximately by storing $a \mod p$ for several random prime numbers $p_i$. If we use $k$ primes chosen independently of the value of $a$, then the representation requires $k \, \lceil c\,\log_2(n) \rceil = O(k \log(n))$ bits to store the values modulo every chosen prime. The probability of a collision on each prime is at most $c \ln(n) / n^{c-1} = O(\ln(n)/n^{c-1})$. To evaluate how the precision increases with $k$ would require further analysis.