Schwartz-Zippel Lemma

度为$d_p$的多项式$p(x)$和度为$d_q$的多项式$q(x)$在$p(x)$和$q(x)$不重合时，最多有$\max (d_p,d_q)$个交点。这个形式在实数域和有限域都成立。

证明非常简单，$p(x)$和q$(x)$的交点的x值满足$p(x)-q(x)=0$,这本身是一个最大为$\max (d_p,d_q)$度的多项式

这产生一个推论，就是如果我们在足够大的范围内取一个随机数作为$x$，如果$p(x)$和$q(x)$不是相同的多项式，那么大概率$p(x)\ne q(x)$。这里的大概率是指只要$x$的随机范围足够大，那么这个概率可以忽略不计。这将多项式相等判定的复杂度从$O(\max (d_p,d_q))$降低为$O(1)$

这个性质在零知识证明的简洁化中得到了广泛的应用。