Freivald's Algorithm: pick a uniform random r∈{0，l}, check whether A(Br)=Cr; if AB C:always correct Theorem(Feivald 1979). For n X n matrices A,B,C,ifAB≠C,for uniform random r∈{0，l}n, Pr[ABr=C1≤2 repeat independently for O(log n)times Total running time:O(n2log n) Correct with high probability (w.h.p.).Freivald’s Algorithm: pick a uniform random ; check whether ; r ∈ {0,1}n A(Br) = Cr Theorem (Feivald 1979). For n × n matrices A, B,C, if AB ≠ C, for uniform random r ∈ {0,1} , n Pr[ABr = Cr] ≤ 1 2 if AB = C: always correct repeat independently for O(log n) times Total running time: Correct with high probability (w.h.p.). O(n2 log n)