-1
$\begingroup$

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 .

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 11 '15 at 22:03
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.