Teste probabilístico de multiplicação de matrizes com erro unilateral

Dadas três matrizes queremos testar se . Suponha que as operações aritméticas e tenham tempo constante quando aplicadas a números de .$A, B,C \in \mathbb{Z}^{n \times n}$$AB \neq C$$+$$-$$\mathbb{Z}$

Como posso declarar um algoritmo com erro unilateral que é executado no tempo e provar sua correção?$O(n^2)$

Eu tentei agora por várias horas, mas não consigo acertar. Eu acho que tenho que usar o fato de que para qualquer no máximo metade dos vetores satisfaz , onde indica o produto escalar .$x \in \mathbb{Z}^n$$s \in S = \left\{1, 0\right\}^n$$x \cdot s = 0$$x \cdot s$$\sum_{i=1}^{n} x_is_i$

Se , então para todos os vetores . Gere vetores aleatoriamente e verifique. Isso é conhecido como algoritmo de Freivalds . Wikipedia tem detalhes.$AB=C$$A(Bx)=Cx$$x$