Freivalds' Algorithm

是一个 PIP (概率证明系统)

环境

算法

选取 随机数 $r\in {\mathbb{F}}_p$，另 $x=\{1,r,r^2,\cdots ,r^{n-1}\}$，只需验证：

$$\begin{array}{rl}y& =Cx\\ z& =A\cdot Bx\\ y& ==z\end{array}$$

运行时间

完备性与可靠性

Discussion