Freivald's Algorithm pick a uniform random r∈{0，l"; check whether A(Br)=Cr; if AB =C,always correct ifAB≠C, letD=AB-C≠0n×n sayD,卡0 2n1 1 PABr-C1-PD.s 2 二 -2 m (Dr)i=>Dikrk =0 D r k=1 i ∑D >=D k≠jFreivald’s Algorithm pick a uniform random r ∈{0,1}n; check whether A(Br) = Cr ; if AB = C, always correct if AB ≠ C, Pr[ABr = Cr] = Pr[Dr = 0] let D = AB ￾ C ￾= 0n￾n D r i (Dr)i = ￾ n k=1 Dikrk =0 rj = ￾ 1 Dij ￾ n k￾=j Dikrk 2n 2n￾1 = 1 2 say Dij ￾= 0 ￾