Theorem 1 (Schwartz, Zippel). Let P ∈ F [ x 1 , x 2 , … , x n ] {\displaystyle P\in F[x_{1},x_{2},\ldots ,x_{n}]} P∈F[x1,x2,…,xn] be a non-zero polynomial of total degree d ≥ 0 over a field F. Let S be a finite subset of F and let r1, r2, …, rn be selected at random independently and uniformly from S. Then
Pr [ P ( r 1 , r 2 , … , r n ) = 0 ] ≤ d ∣ S ∣ . {\displaystyle \Pr[P(r_{1},r_{2},\ldots ,r_{n})=0]\leq {\frac {d}{|S|}}.} Pr[P(r1,r2,…,rn)=0]≤∣S∣d.
即对于d阶多项式，任意随机独立从域S中取所有变量值，则所取变量值所多项式取值为零的概率不高于 d / ∣ S ∣ d/|S| d/∣S∣，当阶数d远小于域范围时，该概率可以忽略。
参考资料： [1] https://en.wikipedia.org/wiki/Schwartz–Zippel_lemma [2] http://www0.cs.ucl.ac.uk/staff/J.Groth/MatrixZK.pdf
