Fingerprinting is one of the ingredients of the probabilistic algorithm for identity testing.

Let \(x\neq 0\) be a \(2^n\)-bit number. Let \(M\) be a random prime number in the range \([0,2^{2n}]\). (Note that \(x\) might be exponentially larger than \(M\).) We will show that \(x\not\equiv 0\bmod M\) with high probability.

How can we choose a random prime number in a certain range? The main point is that prime numbers are fairly frequent. In fact, a random \(2n\)-bit number is prime with probability \(\Omega(1/n)\). Hence, if we sample \(\mathrm{poly}(n)\) random numbers, one of them will be a (random) prime number with high probability. (We don’t actually have to check whether the number is prime because we only have one-sided error.)

Claim: With high probability over the choice of \(M\), we have \(x\not\equiv 0 \bmod M\).

Proof: Let \(p_1,...,p_k\) be the prime factors of \(x\). Since \(x< 2^{2^n}\), we have \(k<2^{n}\) prime factors.

On the other hand, the interval \([0,2^{2n}]\) contains roughly \(2^{2n}/n\gg k\) prime numbers.

If \(x\equiv 0\bmod M\), then \(M\) has to be one of the prime numbers \(p_1,\ldots,p_k\). The probability of this event is about \(k\cdot n/2^{2n}< n/2^n\).