Polynomial Identity testing(PIT)
单元多项式一致性检测
问题
2个d阶多项式$f,g \in 𝔽[x] $，判断$f \equiv g$ ?
因为f,g均为d阶多项式，所以$f-g$也是d阶多项式，所以问题其实就能等价于
判断$f \equiv 0$ ? f是通过黑盒给出，我们可以传入参数得到结果，但无法获知每一项的系数进行简单的比较
重要定理：n阶多项式最多有n个不同的解。
简单随机算法：
给定$S \subseteq 𝔽$，随机从S中选择一个r，判断f(r) = 0 , 如果不等于那么$f \not\equiv 0$，否则判定$f \equiv 0$的错误率就是$Pr[one-side \space error] \le \frac{d}{|S|}$。
将|S|中的元素数量设置成2d个，那么一次随机过程的错误率就降低到了1/2，进行logn次随机过程
$Pr[logn-sides \space error] \le \frac{1}{n}$。
数据通信复杂度
A(Alice) 与 B(Bob)可进行通讯（就是数据交换，以bit的位数来计算交换的信息量）
数据可有一堆0,1的二进制位表示，那么现在A和B中都有n个二进制位的数据，比较两者数据是否一致，数据可能很多，所以n将会达到非常大的级别。
A: $a \in \{0,1\}^n$
B: $b \in \{0,1\}^n$
最naive的方法
B将自己所有的数据 b 全发送给A，那么通信过程中传递的信息bit位数应该是O(n)的级别
随机取数值，通过PIT求解
根据给定的数据，那么很容易就
对A构造一个n-1阶多项式
$f = \sum_{i=0}^{n-1}{a_ix^i}$
对B构造一个n-1阶多项式
$g = \sum_{i=0}^{n-1}{b_ix^i}$
一次随机过程我们定义如下：
在集合{0,1,…,2n-1}中随机选择一个r，那么
$f(r) = g(r) -> f(r)-g(r) = 0 $
$f(r) - g(r)$也是一个n-1阶多项式，那么1元n-1次它最多有n-1个解，所以通过$f(r)-g(r) = 0$判断 $f=g$的错误概率$Pr(one-side \space error) \le (n-1)/2n \le 1/2$
那么进行logn此随机过程之后，错误率将会降到$Pr(logn-sides \space error) \le 1/n$，通讯次数是O(logn)，但是一次通信传递的值是r和g(r)，r的bit位很好计算为O(logn)，但是g(r)可以很大很大，那么通讯用的bit位就会变得很大。
设定有限域降低g(r)bit位
域:
一组元素的集合，以及在集合上的四则运算，构成一个域。其中加法和乘法必须满足交换、结合和分配的规律。加法和乘法具有封闭性，即加法和乘法结果仍然是域中的元素。
域中必须有加法单位元和乘法单位元，且每一个元素都有对应的加法逆元和乘法逆元。但不要求域中的 0有乘法逆元。
有限域:
仅含有限多个元素的域。
定义有限域$ℤ_p=\{0,1,…,p−1\}(p为质数)$，这个有限域的所有元素都是对p取模的，这样就保证了有限域中的所有元素都满足4则运算的要求。实则也能将$ℤ_p$理解为一个对p取模的最小等价类。
一次随机过程:
r从有限域中随机选择一个数字，然后计算g(r)，计算过程中保证对p取模，将r,g(r)传递给A，那么一次通讯过程中传递的数据量为O(2logn) <-> O(logn)级别的。
每次随机过程中虽然答案对p取模了，但是n-1阶多项式$f-g=0$的解集在一个等价类当中依然至多是n-1个。这里要求p是质数的原因很简单，因为p不是质数的时候，很容易出现r^x = 0 (mod p)比如4^i = 0 (mod 8) (i>=2)。
所以一次随机过程的错误概率是$Pr(one-side \space error) \le (n-1)/p$
1.令p>=2n所以$k=\left\lceil log_2(2n) \right\rceil \quad p \in [2^k,2^{k+1}] \quad f,g \in ℤ_p$
那么$Pr(one-side \space error) \le (n-1)/p \le 1/2$
2.令$p \in [n^2,2n^2]$那么一次通讯的错误率就会降到1/n，就不需要多次通讯了。
总的通讯复杂度分析：
上面说了两种情况：
第一种一次随机过程数据通信复杂度是O(logn)，错误率是<=1/2，通过logn次通讯，错误率将降到低于1/n ，数据通信复杂度为$O(log^2n)$
第二种一次通讯错误率就降到了1/n，这次通讯过程中传的数据复杂度为$log_2n^2 = 2log_2n$，所以这个的总的复杂度级别是$O(logn)$更加优秀。
多元多项式一致性检测
Input：$f,g \in 𝔽[x_1,x_2,…,x_n]$ of degree d (d阶多项式)
Output：$f \equiv g$ ?
问题等价于
Input：$f \in 𝔽[x_1,x_2,…,x_n]$ of degree d
Output：$f \equiv 0$ ?
$$
f(x_1,x_2,…,x_n) = \sum_{\begin{matrix} i_1,i_2,…,i_n \ge 0 \ i_1+i_2+…+i_n \le d \end{matrix}}a_{i_1,i_2,..,i_n}x_1^{i_1}x_2^{i_2}…x_n^{i_n}
$$
由此可以看出这里的系数是对应n维的空间，是属于指数增长的。
给定$\vec x = (x_1,x_2,…,x_n)$，那么$f(x_1,x_2,…,x_n) = f(\vec x)$。
随机算法过程
构建$S \subseteq 𝔽$，随机从S集合中选取n个元素（相同的元素可以被多次获取）作为$\vec x$，那么总共取的方法数是$|S|^n$。将这n个元素构成的$\vec x$代入$f(\vec x)$判断是否为0。
这个方法的$Pr[one-side error] \le \frac{d}{|S|}$。
那么方程的解的数量就是总的方法数乘以错误概率$\le |S|^n\frac{d}{|S|} = d|S|^{n-1}$
错误概率上界的证明
$$
\begin{aligned}
f(x_1,x_2,…,x_n) &= \sum_{i=0}^d{x_n^i}f_i(x_1,x_2,…,x_{n-1}) \\
& = g_{x_1,x_2,…,x_{n-1}}(x_n)
\end{aligned}
$$
关于错误概率给定的结论是：$f \not\equiv 0 \quad => \quad Pr[f(x_1,x_2,…,x_n)] = 0] \le \frac{d}{|S|}$。
通过数学归纳法证明，那么这个结论在推导过程中都是可用的：
1.n=1 单元多项式 $Pr[f(x)] = 0] \le \frac{d}{|S|}$没有问题
2.对于n>1：
假设k是f中$x^n$的最高幂次
$$
\begin{aligned}
f(x_1,x_2,…,x_n) &= \sum_{i=0}^k{x_n^i}f_i(x_1,x_2,…,x_{n-1}) \\
& = x_n^kf_k(x_1,x_2,…,x_{n-1})+\sum_{i=0}^{k-1}{x_n^i}f_i(x_1,x_2,…,x_{n-1}) \\
\\
全概率公式:P[f(x_1,x_2,…,x_n) = 0] & = P[f(x_1,x_2,…,x_n) = 0 \space | \space f_k(x_1,x_2,…,x_{n-1}) = 0]∗P[f_k(x_1,x_2,…,x_{n-1}) = 0] \\
& + P[f(x_1,x_2,…,x_n) = 0 \space | \space f_k(x_1,x_2,…,x_{n-1}) \ne 0]∗P[f_k(x_1,x_2,…,x_{n-1}) \ne 0]
\end{aligned}
$$
根据前面的概念可知(1) $P[f_k(x_1,x_2,…,x_{n-1}) = 0] \le \frac{d-k}{|S|}$
根据数学归纳法来说，得知结论$Pr[f(r_1,r_2,…,r_{n})] \le d/|S|$，那么在这里，P[f_k(x_1,x_2,…,x_{n-1}) = 0]可理解为degree为d-k的n-1元多项式，所以概率$\le (d-k)/|S|$。
(2) $Pr[f(\vec r) = 0 | f_k(x_1,x_2,…,x_{n-1}) \ne 0] = Pr[g_{r_1,r_2,…,r_{n-1}}(r_n)=0|f_k(x_1,x_2,…,x_{n-1}) \ne 0] \le k/|S|$
因为条件概率中的条件限制了$f$的最高阶是k，根据结论那么该多项式的解集最多为k/|S|
另外两项的概率默认小于等于1，所以总的概率就是$\le (d-k)/|S| + k/|S| = d/|S|$
那么满足数学归纳法的递推关系，所以结论正确。
数据通信数据量复杂度随机抽取质数求解
问题和前面的数据通讯描述一致，给定的n个0,1就可以理解成对应的十进制数
A: $a \in [2^n]$
B: $b \in [2^n]$
判断a，b是否一致。
算法流程
随机从[0,k]抽取一个质数p，B将p和b % p传递给A，然后A通过a % p 和b % p 进行比较。这传递的信息占用的bit位数符合O(logp)。
算法分析
$$
if \quad a=b => a \equiv b \space (mod \space p) \\
if \quad a \ne b: \quad Pr[a \equiv b(mod \space p)] \le ? \\
z=|a-b|\ne 0: Pr[z(mod \space p)] \le ?
$$
$Pr[z \space mod \space p = 0] = \frac{z的质因子个数 \le n}{小于等于k的质数数量 = \pi k \sim k/lnk}$。简单理解就是z中的质因子在分母对应的质数出现过的概率。
令$k = n^2$那么$Pr[z \space mod \space p = 0] = \frac{nlnk}{k} = \frac{2nlnn}{n^2} = \frac{2lnn}{n}$。
不同集合的一致性检测
问题
给定multisets A={$a_1,a_2,…,a_n$},B={$b_1,b_2,…,b_n$}。所有集合中的元素均属于{1,2,…,n}。
判断A和B是否完全相同。
这个问题不能将集合转化成多项式然后通过随机方法求解。因为集合中的元素是可以改变位置的。
那么就可以转化成
$$
A = {a_1,a_2,…,a_n} =>f_A(x) = \prod_{i=1}^n(x-a_i) \in ℤ_p[x] \space for \space prime \space p(to \space be \space specified)。 \\
FING(A) = f_A(r) 均匀分布下随机选取一个r\in ℤ_p \\
FING(B) = f_B(r) 均匀分布下随机选取一个r\in ℤ_p
$$
错误率就是在A和B不相同的情况下，仍然出现$FING(A) = FING(B)$的概率，分两种情况：
定义素数p在[L,U]范围内 $U = 2L = (nlogn)^2$
因为集合元素都在1~n内，根据乘法公式可得$f_A(x) \le n^n$
$$
\begin{cases}
- f_A \equiv f_B (mod \space p)(表示对应系数一致，那么f_A-f_B中得到的系数存在c能整除p) \\
Pr[c \space mod \space p=0] \le \frac{c的素数因子个数}{[L,U]范围内素数个数} \le \frac{nlog_2n}{\pi(U)-\pi(L)} \sim \frac{nlog_2n}{U/lnU-L/lnL} = O(1/n) \quad c \le n^n \\ - f_A \not\equiv f_B (mod \space p) \space f_A(r) = f_B(r) =>Pr \le n/p \le n/L = O(1/n)
\end{cases}
$$
Reference
1.南大高级算法-Fingerprinting主页/Fingerprinting)
2.课堂内容课件Fingerprinting.pdf
