#The Schwartz-Zippel Algorithm

##Problem: Testing Polynomial Identities
判断两个多项式\(P(x_0, x_1, …, x_n),Q(x_0, x_1, …, x_n)\)在有限取值空间里是不是等价的.

##Solution: A Monte Carlo algorithm
随机取值测试,看看P,Q是不是一样.

##Analysis and Proof

d是P,Q中多项式最大的度,S是取值空间,如果P,Q不一致,而随机测试碰巧相等的概率是:d/|S|.

如果自变量只有一个证明比较简单,\(H(x) = P(x) – Q(x) = w_n * x^n + … + w_0\).

那么H(x)最多有n个解,取值空间大小是|S|,碰巧的可能是n/|S|.

如果有多个变量的证明也是类似的.归纳法证明.