南京大学：《随机算法 Randomized Algorithms》课程教学资源（课件讲稿）Finger printing

Polynomial ldentity Testing (PIT) Input:f,gEF[1,22,...,n]of degree d Output:f=g? F1,2,...,:ring of n-variate polynomials over fieldF f∈F[x1,2,,cn: f(r1,2,,xn)= 21 Qil,i2,...,in 2.…n i1,i2,…,in≥0 degree of f:maximum i1+i2+..+in with a,i2...0

Polynomial Identity Testing (PIT) Input: of degree d Output: f ￾ g? f,g 2 F[x1, x2,...,xn] F[x1, x2,...,xn] : ring of n-variate polynomials over field F f(x1, x2,...,xn) = X i1,i2,...,in￾0 ai1,i2,...,in xi1 1 xi2 2 ··· xin n degree of f : maximum i1 + i2 + ··· + in ai1,i2,...,in with 6= 0 f 2 F[x1, x2,...,xn] :

Input:f,geF[1,22,...,n]of degree d Output:f g? equivalently: Input:fEF[1,22,...,n]of degree d Output:f≡0？ fis given as block-box:given any=(1,x2,...,n) returns f(z) or as product from:e.g.Vandermonde determinant X1 n- 1 -1 T2 2 T T2 M= f(=det(M)=Π(r-x) In 喝 x-1 j<i

Input: of degree d Output: f ￾ g? f,g 2 F[x1, x2,...,xn] Input: of degree d Output: f ￾ 0? f 2 F[x1, x2,...,xn] equivalently: f is given as block-box: given any ~ x = (x1, x2,...,xn) returns f(~ x) or as product from: Vandermonde determinant M = 2 6 6 6 4 1 x1 x2 1 ... xn￾1 1 1 x2 x2 2 ... xn￾1 2 . . . . . . . . . ... . . . 1 xn x2 n ... xn￾1 n 3 7 7 7 5 f(~ x) = det(M) = Y j<i (xi ￾ xj ) e.g

Input:fF[1,22,...,n]of degree d Output:f≡0？ fix an arbitrary S F pick random ri,r2,...,mnES uniformly and independently at random; check whether f(ri,r2,...rn)=0; f=0f(r1,r2,.,rn)=0

Input: of degree d Output: f ￾ 0? f 2 F[x1, x2,...,xn] pick random r1, r2, ... , rn ∈S uniformly and independently at random; check whether f(r1, r2, ... , rn) = 0 ; fix an arbitrary S ✓ F f ⌘ 0 f(r1, r2,...,rn)=0

Input:a polynomial fe]of degree d Output:f三0？ fix an arbitrary SF pick a uniform random r ES; check whether fr)=0; f≡0>f(r)=0 Fundamental Theorem of Algebra: A degree d polynomial has at most d roots. f丰0>Prf(r)=0]≤ d Is]

A degree d polynomial has at most d roots. Fundamental Theorem of Algebra: pick a uniform random r ∈S; check whether f(r) = 0 ; Input: a polynomial of degree d Output: f ￾ F[x] f ￾ 0? fix an arbitrary S ✓ F f ⌘ 0 f(r)=0 f 6⌘ 0 Pr[f(r) = 0]  d |S|

Input:fF[1,22,...,n]of degree d Output:f≡0？ fix an arbitrary S F pick random ri,r2,...,rES uniformly and independently at random; check whether f(ri,r2,...,r)=0 f三0>f(r,r2,,rn)=0 Schwartz-Zippel Theorem d f丰0>Pr[f(1,r2,,rn)=0]≤ IS

Input: of degree d Output: f ￾ 0? f 2 F[x1, x2,...,xn] pick random r1, r2, ... , rn ∈S uniformly and independently at random; check whether f(r1, r2, ... , rn) = 0 ; fix an arbitrary S ✓ F Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0]  d |S| f 6⌘ 0 f ⌘ 0 f(r1, r2,...,rn)=0

Schwartz-Zippel Theorem d ∫丰0！ >Pr[f(r1,r2,,rn)=0]≤ induction on n: basis: n=1 single-variate case,proved by the fundamental Theorem of algebra I.H.:Schwartz-Zippel Thm is true for all smaller n

Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0]  d |S| f 6⌘ 0 induction on n : basis: n=1 single-variate case, proved by the fundamental Theorem of algebra I.H.: Schwartz-Zippel Thm is true for all smaller n

Schwartz-Zippel Theorem d ∫丰0 >Pr[f(r1,r2,,rn)=0]≤ s induction step: k:highest power ofxn inf ∫fk丰0 degree of fr≤d-k k f(c1,x2,,xn）=xf(1,x2,…,n-l） i=0 =xhfk(x1,c2,,xn-1）+f(ac1,2,,n） k-1 where f(ar1,tr2,…,cn）=xf(c1,x2,…,n-1） i=0 highest power of xn in f<

f(x1, x2,...,xn) = X k i=0 xi nfi(x1, x2,...,xn￾1) k: highest power of xn in f fk 6⌘ 0 degree of fk  d ￾ k n = xk nfk(x1, x2,...,xn￾1) + ¯f(x1, x2,...,xn) ¯f(x1, x2,...,xn) = k X￾1 i=0 xi n where fi(x1, x2,...,xn￾1) highest power of xn in ¯f <k Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0]  d |S| f 6⌘ 0 induction step:

Schwartz-Zippel Theorem d ∫丰0 >Pr[f(r1,r2,,rn)=0]≤ S f(ac1,x2,,xn）=axhf(a1,2,…,xn-1）+f(ac1,2,,xn) 了fk丰0 degree of f≤d-k highest power of xn in f☐s SI =Pr[f(=0|fk(r1,,rn-1)=0]Pr[f(r1,.,rn-1）=0] +Pr[f(=0|fk(r1,.,rn-1)≠0]Pr[fk(r1,,rn-1)≠0] =Prg1…m-1(n)=0|fk(1,,n-1)≠0]≤ k where91,xn-1(cn）=f(c1,,xn）

highest power of xn in ¯f <k fk 6⌘ 0 degree of fk  d ￾ k = xk nfk(x1, x2,...,xn￾1) + ¯f(x1, x2,...,xn) Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0]  d |S| f 6⌘ 0 f(x1, x2,...,xn) n law of total probability: Pr[f(r1, r2,...,rn) = 0] = Pr[f(~ r)=0 | fk(r1,...,rn￾1) = 0] · Pr[fk(r1,...,rn￾1) = 0] + Pr[f(~ r)=0 | fk(r1,...,rn￾1) 6= 0] · Pr[fk(r1,...,rn￾1) 6= 0] I.H.  d ￾ k |S|  k |S| gx1,...,xn￾1 where (xn) = f(x1,...,xn) = Pr[gr1,...,rn￾1 (rn)=0 | fk(r1,...,rn￾1) 6= 0]

Schwartz-Zippel Theorem d f≠0>Pr[f(r1,r2,,rn)=0≤ IS Prf1,r2,,m）=0】≤S+ d-k k d S] ISI

Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0]  d |S| f 6⌘ 0 Pr[f(r1, r2,...,rn) = 0]  d ￾ k |S| + k |S| = d |S|

Input:fF[1,22,...,n]of degree d Output:f≡0？ fix an arbitrary S F pick random ri,r2,...,rES uniformly and independently at random; check whether f(ri,r2,...,r)=0 f三0>f(r,r2,,rn)=0 Schwartz-Zippel Theorem d f丰0>Pr[f(1,r2,,rn)=0]≤ IS

Input: of degree d Output: f ￾ 0? f 2 F[x1, x2,...,xn] pick random r1, r2, ... , rn ∈S uniformly and independently at random; check whether f(r1, r2, ... , rn) = 0 ; fix an arbitrary S ✓ F Schwartz-Zippel Theorem Pr[f(r1, r2,...,rn) = 0]  d |S| f 6⌘ 0 f ⌘ 0 f(r1, r2,...,rn)=0