多项式恒等式测试

每个门只做它在这个点上的运算 ​

设两个前驱门分别代表f和g。若已保存f(r)、g(r)，当前加法门只需相加，乘法门只需相乘，无须知道它们各有多少项。拓扑遍历的不变量是：处理过的每个门，保存值恰等于该门形式多项式在r处的值。

变量和常数门满足不变量。对加、减、乘门，代入与这些运算相容，所以前驱值正确就推出当前值正确。共享子电路只计算一次；用递归反复展开共享节点会把DAG误当成树。

零点是可以碰到的，非零见证不能伪装 ​

若 $P_C=0$，所有点值必为零；算法不会返回错误的NONZERO。如果P非零，只有碰巧落在其零点集合里才漏检。因而多轮测试取“是否至少一次非零”，无需多数投票。

例如真实P=x时，代入x=0没有发现差异，代入x=3就给出确定见证。返回3并不说明算法猜得更准，而是提供了可独立验证的反例点。

一个逐门复算的恒等式 ​

在 ${\mathbb{F}}_{17}$ 上比较

取(x,y)=(3,5)。左边先得x+y=8，再得64≡13；右边的三项为9、30≡13、25≡8，相加30≡13，差为0。把B改成B+x，同一个点的差变成−3≡14，立刻返回NONZERO。

电路中x、y可被多条边引用，输出差的形式次数上界D=2。取 $S=\{0,\dots ,15\}$，每个坐标恰用4个公平随机位；四轮一般漏检界为 $(2/16{)}^4=1/4096$。对于刚才改动后的特定差−x，真实单轮漏检率只有1/16，但程序无需先化简到−x才有保证。

小特征需要保留，取模不能随意替换 ​

在 ${\mathbb{F}}_2$ 上，P=x²−x不是形式零多项式，却在0和1上都为零。重复一千轮仍检测不到。沿用有限域理路有限域Finite field · Galois field底层集合有限的域。的扩域构造，令 ${\mathbb{F}}_4={\mathbb{F}}_2[\alpha ]/({\alpha }^2+\alpha +1)$；于是 $P(\alpha )={\alpha }^2+\alpha =1$。底域到扩域的嵌入保持非零系数，问题没有改变。

反过来，把整数电路直接模p化简只能测试它在特征p下的像。例如整数常数p本来非零，却被该取模变成零。要由模素数测试推出有理数或整数上的一般PIT，还需控制分母、系数大小和坏素数；本页的域内算法没有免费解决这一转换。

分母、浮点和自适应电路不在当前保证里 ​

除法门可能在代入点分母为零，即使表达式在别处有定义。要纳入除法，须另行处理分母和定义域，不能把异常值当成输出零。参考实现只接受const、var、add、sub、mul五种门。

浮点小数中的“等于零”会受舍入与消去误差影响；这里用精确有限域运算。参考程序的常数是整数对指定素数取余，素数限于明列并已验证的六个值，不把一般素性判定或任意扩域构造藏进一次函数调用。

若对手在看见本轮随机点后才提交电路，可以提交在该点恰为零的非零多项式。此时应改变交互协议，而非继续引用固定输入的漏检界。

时间、随机位和存储分别计数 ​

设电路有s个门、n个变量。验证拓扑前驱并计算次数上界需要O(s)个整数操作；即使连续平方使D达到指数大小，次数整数的位长仍为O(s)。每轮求值需要O(s+n)个域操作及O(s+n)个域元素空间，t轮总计O(t(s+n))域操作；程序一次只保留当前轮全部门值，日志另保留t个点及输出值，占O(t(n+1))个域元素。

对b位素数域，约化后每个门值占O(b)位。朴素整数乘法和取模可按O(b²)位操作收费，加法更便宜；于是求值部分为O(t(s+n)b²)，另加读取常数、处理索引、次数大整数与生成随机位的成本。固定机器字模型下b受字长限制，才可把域运算近似看作常数。

为得到有界随机位接口，可以选择 $|S|=2^{\ell }\le |F|$，并提供从ℓ位串到S的一一编码。素数域中可取S={0,…,2^ℓ−1}。每轮恰需nℓ位；若还满足 $2^{\ell }\ge 2D$，每轮漏检至多1/2。对于小域，应提供足够大的同特征扩域及其运算。域构造与编码的位成本必须另计，不能只靠“抽一个域元素”声称全流程多项式时间。

单边误差方向取决于问的是零还是非零 ​

若把问题写成“是否非零”，零输入永不被接受，非零输入以至少1/2概率被接受，这对应RP的单边接受方向理路复杂度类 RPComplexity class RP具有单边误差多项式时间随机算法的语言类。。若问“是否恒等于零”，把全部零值当成接受，则方向反过来，是coRP。这里的复杂度归类以域表示、抽样和次数预算都能在相应输入长度的多项式资源内实现为前提。

Tutte矩阵理路Tutte矩阵Tutte matrix · 图匹配的Tutte矩阵以反对称边变量矩阵编码一般图完美匹配，证明随机行列式判定，并用隔离权与二进阶主子式提取可验真匹配。给出具体的代数判定接口：无需把行列式展开成指数多个项，先代入边变量，再用精确消元计算数值行列式。电路PIT与该矩阵例子共享零点界，但它们的求值器可以不同。

终点迁移：给出见证，而非只打印布尔值 ​

代数随机化证书终点要求提交电路、底域、D、S、每轮代入点与输出值。把最后一个−x改成−(x−y)，重新检查实际零点率与统一D/|S|界；再说明为何把两个坐标强制取相同值会完全遮住这个改动。