Schwartz-Zippel Lemma

1. 引言

对于多项式 f ( x 1 , x 2 , … , x n ) f(x_1,x_2,…,x_n) f(x1​,x2​,…,xn​)，其系数在 F F F field域内，如何判断 f f f是否为零多项式？ 第一反应是将 f ( x 1 , x 2 , … , x n ) f(x_1,x_2,…,x_n) f(x1​,x2​,…,xn​)完全展开，只要其中任一系数不为0，则其为非零多项式。当对多项式展开的复杂度较高时，则可任意取一组值 r 1 , r 2 , … , r n r_1,r_2,…,r_n r1​,r2​,…,rn​，若 f ( r 1 , r 2 , … , r n ) ! = 0 f(r_1,r_2,…,r_n)!=0 f(r1​,r2​,…,rn​)!=0，则 f f f为非零多项式。反之则不成立。 Schwartz-Zippel lemma可用于判断 f = 0 f=0 f=0的概率上限的方法，具体内容为： 引申出来为：【见论文《Efficient Zero-Knowledge Argument for Correctness of a Shuffle 2012》，该特性可用于判断两个多项式是否完全相同，进而已可引申为判断两个vector是否完全相同。】 举例如下： 参考资料： [1] https://brilliant.org/wiki/schwartz-zippel-lemma/