了解使用随机算法的多项式平等测试 -- algorithms 领域 和 probability-theory 领域 和 randomized-algorithms 领域 和 probabilistic-algorithms 领域 cs 相关 的问题

Understanding polynomial equality testing using randomized algorithms

-1 问题 1）在步骤1中，我认为应该选择$c cdot n$，因为如果$m = 2 ^ {n-1}$，它会击败目的，我们最终以$o（n）$，而不是$o（ log n）$;右？

2）在步骤2中，我们正在挑选素数。为什么需要素质？为什么我们不能只选择$M$？

3）在步骤3＆amp; 4，我们选择一个随机值$r$，并计算$a（r）（ mod p）$。为什么我们不能简单地计算$a_ {dec} mod p$？ $a_ {dec}$是二进制字符串$a$的十进制表示。然后，我们可以简单地比较$a_ {dec} mod p$和$b_ {dec} mod p$。

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.

回答列表

1 