Fast checking Matrix multiplication in mod 10 I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In other words, return the result of expression (A x B) mod 10 == C.

For example:

$\qquad A = \begin{bmatrix}
 0 &amp; 5 &amp; 8 \\ 
 1 &amp; 4 &amp; 9 \\ 
 2 &amp; 3 &amp; 3
\end{bmatrix}\qquad
B = \begin{bmatrix}
 3 &amp; 5 &amp; 0 \\ 
 1 &amp; 2 &amp; 6 \\ 
 3 &amp; 7 &amp; 0
\end{bmatrix}\qquad 
C = \begin{bmatrix}
 9 &amp; 6 &amp; 0 \\ 
 4 &amp; 6 &amp; 4 \\ 
 8 &amp; 7 &amp; 8
\end{bmatrix}$

return: TRUE

If

$\qquad C = \begin{bmatrix}
 1 &amp; 6 &amp; 0 \\ 
 4 &amp; 6 &amp; 4 \\ 
 8 &amp; 7 &amp; 8
\end{bmatrix}$

return: FALSE, since the element C(1, 1) must be 9.

Time limit is 1s, pretty strict. Please gives me some idea how to solve the problem efficiently; is it possible time $O(N^2)$?
I got Accepted by using Freivald's algorithm as suggested by @David Richerby. Thank you very much !

I have not tested the brute-force solution using Coppersmith-Winograd algorithm yet. Will report in a couple of days, by the way I think it might not get Accepted but possibly will gain a fairly amount of points.

For those who want to check your implementation, submit your code on http://vn.spoj.com/problems/VMATRIX/. The problem statement is in Vietnamese, so here is the short description of input format:


  
  First line is number of testcase (the example gives 2 testcases)
  For each testcase: 
  the first line is size of 3 matrices, N. In 20% testcase N &lt;= 100. 
  next N * N lines: matrix A
  next N * N lines: matrix B
  next N * N lines: matrix C
  


Output: YES or NO for the result.