Freivald's Algorithm: pick a uniform random r∈{0，l}, check whether A(Br)=Cr; fAB≠C: letD=AB-C卡0xn suppose Dii卡0 1 Pr[ABr =Cr]=Pr[Dr=0]< 三 2 (Dr,=∑D4=0 D r k=1 i 之2Freivald’s Algorithm: pick a uniform random ; check whether ; r ∈ {0,1}n A(Br) = Cr if AB ≠ C: let D = AB − C ≠ 0n×n D r i suppose Dij ≠ 0 Pr[ABr = Cr] = Pr[Dr = 0] ≤ (Dr)i = n ∑ k=1 Dikrk = 0 rj = − 1 Dij ∑ k≠j Dikrk = 1 2 2 n 2n−1