Lesson 7

In fact, any deterministic protocol (not just one-round) requires Alice and Bob to exchange at least \(n\) bits in the worst case to solve the problem.

We now show that Alice and Bob can use randomness to obtain the correct answer with high probability while transmitting only \(O(\log n)\) bits. This is an exponential improvement! Again, we use a fingerprint, and this time the fingerprint will be a remainder modulo some number. Alice chooses a random prime number \(p\) from the interval \([1..t]\) (the value of the parameter \(t\) will be chosen later) and sends Bob \(p\) and \(a \bmod p\). Bob compares the received remainder with \(b \bmod p\). If the remainders differ, then of course \(a \neq b\). But if \(a \bmod p = b \bmod p\), the strings may still differ. This happens when \(p\) divides \(a-b\). It is easy to see that \(a-b < 2^{n}\), and therefore this number can have at most \(n\) distinct prime divisors (if there were more, then their product \(2\cdot 3 \cdot 5 \dotsb\) would exceed \(2^{n}\)). The total number of primes in the interval \([1..t]\) is about \[\frac{t}{\ln t}\] (see the prime number theorem). If we take \(t=n^{2}\log n\), then the error probability of the protocol can be estimated from above as \[\frac{n}{t/\ln t}=O\left(\frac{1}{n}\right) \ .\] The complexity of the protocol is \(2\log_{2} t=O(\log n)\).