Understanding polynomial equality testing using randomized algorithms

A file is downloaded from a server and is represented as $a = \{0, 1\}^n$. The server has that file as $b = \{0, 1\}^n$. We want to ensure a degree of certainty that $a=b$, using a randomized algorithm.

So below is the procedure referenced from this lecture pdf . I can't get my head around why some of the steps are necessary. So these are my questions.

1) In step 1, I believe $M$ should be chosen as $c \cdot n$, since if $M = 2^{n-1}$, it would defeat the purpose and we end up with $O(n)$, instead of $O(\log n)$; right ?

2) In step 2, we are picking a prime. Why is a prime necessary ? why can't we simply choose $M$ ?

3) In steps 3 & 4, we pick a random value $r$ and compute $a(r)(\mod p)$. Why can't we simply compute $a_{dec} \mod p$ ? where $a_{dec}$ is the decimal representation of the binary string $a$. Then, we could simply compare $a_{dec} \mod p$ and $b_{dec} \mod p$.

If you could lay down an example of how this works, it would be much appreciated. Let's say we have $a = 101100$ and $b = 111100$, how do we go about comparing them using this algorithm ?

Thanks.

• Hopefully your lecture notes contain a proof of correctness of this algorithm. Go over the proof and see that you understand it, and then you can try to answer your questions on your own. – Yuval Filmus Jan 11 '15 at 22:03

Your lecture note contains the answer to your questions. Here are some hints.

1) In step 1, I believe $M$ should be chosen as $c \cdot n$, since if $M=2^n − 1$, it would defeat the purpose and we end up with $O(n)$, instead of $O(\log n)$; right?

Yes. That is exactly why we choose to work over a finite field (modulo a prime $p$) instead of over the whole integers. We do all calculations $\bmod p$, which guarantees that we never need more than $O(\log p)$ bits.

2) In step 2, we are picking a prime. Why is a prime necessary ? why can't we simply choose $M$?

We have decided to work over a finite field modulo a prime $p$. $p$ is used in step 4) and step 5).

3) In steps 3 & 4, we pick a random value $r$ and compute $a(r)(\bmod p)$. Why can't we simply compute $a_{dec} \bmod p$?

We are thinking of a string as a polynomial: $$a(x) = \sum_{i=1}^{n} a_i x^i$$ and evaluate it at $r$. After all, we are doing Polynomial Identity Testing. However, $a_{dec}$ has nothing to do with $r$ and polynomial (evaluation).