在 GF(p) 上，若两个多项式的乘积是零函数，则至少有一个是零多项式。
错误。有限域上的函数环存在零因子，例如 p=2 时 f(x)=1+x 与 g(x)=x 均非零，但乘积在 GF(2) 的每一点都为零。这与实数域上非零多项式只有有限个根不同。
CS70 · 第 6 讲
本讲在有限域 GF(p) 上重新审视多项式的根界与等价性，建立 Lagrange 插值与中国剩余定理的统一视角，并展示多项式如何同时支撑起秘密共享与纠错码两个应用方向：从 Shamir 门限方案到 Berlekamp-Welch 解码。
在有限域 \(\mathrm{GF}(p)\)（\(p\) 为素数）上，我们考察系数对 \(p\) 取模的多项式。两个多项式 \(f\) 与 \(g\) 称为等价的，如果对每个 \(x\in\mathrm{GF}(p)\) 都有 \(f(x)=g(x)\)。等价不意味着系数相同，这是本节所有讨论的出发点。
费马小定理提供了化简多项式的关键工具：对任意 \(a\in\mathrm{GF}(p)\) 有 \(a^p\equiv a\pmod p\)，因此多项式 \(x^p\) 与 \(x\) 在 \(\mathrm{GF}(p)\) 上等价。更一般地，若 \(d\ge p\)，由 \(x^d=x^{d-p}\cdot x^p\equiv x^{d-p}\cdot x=x^{d-(p-1)}\) 可把次数降低 \(p-1\)；重复此步骤直到次数小于 \(p\)。于是每个多项式都等价于一个次数 \(<p\) 的多项式。
域上多项式最重要的根界：次数为 \(d\) 的非零多项式在 \(\mathrm{GF}(p)\) 中至多有 \(d\) 个根。证明对 \(d\) 归纳：若 \(r\) 是根，则由因式定理 \(f(x)=(x-r)q(x)\)，\(\deg q=d-1\)，\(q\) 至多有 \(d-1\) 根，故 \(f\) 至多有 \(d\) 根。这个界是紧的：\(x^{p-1}-1\) 恰好以 \(\mathrm{GF}(p)\) 的全部 \(p-1\) 个非零元为根。
与实数域不同，\(\mathrm{GF}(p)\) 上的函数环存在零因子：两个非零多项式的乘积可以是零函数。例如 \(p=2\) 时取 \(f(x)=1+x\) 与 \(g(x)=x\)（在 \(\mathrm{GF}(2)\) 中 \(1+x\) 即 \(1-x\)），则 \((f\cdot g)(0)=0\) 且 \((f\cdot g)(1)=0\)，故乘积为零函数，但 \(f\) 与 \(g\) 均非零多项式。原因是有限域上非零多项式只有有限个根，可让不同多项式各自覆盖一部分点。
化简 \(f(x)=x^7+3x^3\) 为 \(\mathrm{GF}(5)\) 上次数 \(<5\) 的等价多项式。由 \(x^5\equiv x\) 得 \(x^7=x^5\cdot x^2\equiv x\cdot x^2=x^3\)，于是 \(f(x)\equiv x^3+3x^3=4x^3\pmod 5\)，次数为 \(3\)。
计数问题：求 \(\mathrm{GF}(5)\) 上次数恰好为 \(d=3\) 且满足 \(f(0)=2\) 的多项式个数。设 \(f(x)=c_3x^3+c_2x^2+c_1x+c_0\)。条件 \(f(0)=2\) 固定 \(c_0=2\)；次数恰好为 \(3\) 要求首项系数 \(c_3\in\{1,2,3,4\}\)（\(4\) 种选择）；\(c_1,c_2\) 可取 \(\mathrm{GF}(5)\) 中任意值（各 \(5\) 种）。故共有 \(4\cdot 5^2=100\) 个这样的多项式。
Lagrange 插值解决如下问题：给定 \(d+1\) 个互异点 \((x_0,y_0),\ldots,(x_d,y_d)\)，其中 \(x_i\) 两两不同，求一个次数 \(\le d\) 的多项式 \(p\) 使得 \(p(x_i)=y_i\) 对所有 \(i\) 成立。
构造 Lagrange 基多项式 \[L_i(x)=\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}.\] 分母是 \(d\) 个非零差值 \(x_i-x_j\) 的乘积，在域中可逆；分子在 \(x_i\) 处取值恰等于分母，故 \(L_i(x_i)=1\)，且当 \(j\neq i\) 时 \(L_i(x_j)=0\)。
插值公式为 \[p(x)=\sum_{i=0}^{d} y_i\cdot L_i(x).\] 由构造即得 \(p(x_i)=y_i\)。此方法直接给出满足条件的多项式，无需解线性方程组。
唯一性：若 \(p,q\) 均为次数 \(\le d\) 且在同 \(d+1\) 个点上取值相同，则 \(p-q\) 有 \(d+1\) 个根但次数 \(\le d\)，由根界知 \(p-q\) 为零多项式，故 \(p=q\)。注意唯一性依赖次数上界 \(\le d\)；若允许更高次，则可任意加上 \(\prod_{i}(x-x_i)\) 的倍数。
在 \(\mathrm{GF}(7)\) 上求经过点 \((0,1),(1,0),(2,4)\) 的唯一次数 \(\le 2\) 多项式。
计算三个 Lagrange 基（利用 \(2^{-1}\equiv 4\pmod 7\)）： \[L_0(x)=\frac{(x-1)(x-2)}{(0-1)(0-2)}=\frac{(x-1)(x-2)}{2}\equiv 4(x-1)(x-2)\equiv 4x^2+2x+1\pmod 7,\] \[L_1(x)=\frac{x(x-2)}{(1-0)(1-2)}=\frac{x(x-2)}{-1}\equiv 6x^2+2x\pmod 7,\] \[L_2(x)=\frac{x(x-1)}{(2-0)(2-1)}=\frac{x(x-1)}{2}\equiv 4x^2+3x\pmod 7.\]
于是 \[p(x)=1\cdot L_0(x)+0\cdot L_1(x)+4\cdot L_2(x)\equiv (4x^2+2x+1)+(2x^2+5x)\equiv 6x^2+1\pmod 7.\]
验证：\(p(0)=1\)，\(p(1)=6+1\equiv 0\)，\(p(2)=6\cdot 4+1=25\equiv 4\pmod 7\)，与给定点一致。
设 \(n_1,\ldots,n_k\) 两两互素。中国剩余定理（CRT）断言：对任意整数 \(a_1,\ldots,a_k\)，同余方程组 \(x\equiv a_i\pmod{n_i}\) 必有解，且任意两个解在模 \(N=n_1\cdots n_k\) 下同余。
先证 \(k=2\)。由 \(\gcd(n_1,n_2)=1\)，扩展欧几里得算法给出整数 \(u,v\) 满足 \(u\cdot n_1+v\cdot n_2=1\)。定义 \(e_1=v\cdot n_2\) 与 \(e_2=u\cdot n_1\)。关键观察：\(e_1=v\cdot n_2=1-u\cdot n_1\equiv 1\pmod{n_1}\)，且 \(e_1\) 是 \(n_2\) 的倍数故 \(\equiv 0\pmod{n_2}\)；对称地，\(e_2\equiv 0\pmod{n_1}\) 且 \(e_2\equiv 1\pmod{n_2}\)。这两个基解各自"点亮"一个模数而熄灭另一个。
通解为 \(x=a_1\cdot e_1+a_2\cdot e_2\)。验证：模 \(n_1\) 得 \(a_1\cdot 1+a_2\cdot 0\equiv a_1\)，模 \(n_2\) 得 \(a_1\cdot 0+a_2\cdot 1\equiv a_2\)。若 \(x,x'\) 均为解，则 \(x-x'\) 同时被 \(n_1,n_2\) 整除，由互素被 \(n_1n_2\) 整除，故解在模 \(n_1n_2\) 下唯一。对一般 \(k\) 归纳即得完整 CRT。
多项式版本：将整数换为多项式，模 \(n_i\) 换为模 \((x-x_i)\)。同余式 \(p(x)\equiv y_i\pmod{(x-x_i)}\) 意味着 \(p(x)-y_i\) 被 \((x-x_i)\) 整除，即 \(p(x_i)=y_i\)。互异 \(x_i\) 保证 \((x-x_i)\) 两两互素。多项式 CRT 给出在模 \(\prod_i(x-x_i)\) 下唯一的多项式——也就是次数 \(<k\) 意义下唯一的多项式。这正是 Lagrange 插值的存在唯一性结论，二者是同一代数事实的两种表述。
求解方程组 \(x\equiv 2\pmod 3\)，\(x\equiv 3\pmod 5\)，\(x\equiv 2\pmod 7\)。
第一步合并模 \(3\) 与模 \(5\)：\(\gcd(3,5)=1\)，\(2\cdot 3+(-1)\cdot 5=1\)，故 \(u=2,v=-1\)。基解 \(e_1=v\cdot 5=-5\equiv 1\pmod 3\) 且 \(\equiv 0\pmod 5\)，\(e_2=u\cdot 3=6\equiv 0\pmod 3\) 且 \(\equiv 1\pmod 5\)。得 \(x_{12}=2\cdot(-5)+3\cdot 6=8\equiv 8\pmod{15}\)。
第二步合并模 \(15\) 与模 \(7\)：\(\gcd(15,7)=1\)，\(1\cdot 15+(-2)\cdot 7=1\)，故 \(u=1,v=-2\)。基解 \(e_1=-2\cdot 7=-14\equiv 1\pmod{15}\) 且 \(\equiv 0\pmod 7\)，\(e_2=1\cdot 15\equiv 1\pmod 7\) 且 \(\equiv 0\pmod{15}\)。最终解 \(x=8\cdot(-14)+2\cdot 15=-82\equiv 23\pmod{105}\)。
验证：\(23\bmod 3=2\)，\(23\bmod 5=3\)，\(23\bmod 7=2\)。若改用 Lagrange 插值语言，我们正是在逐次构造在每个模数（点）处取指定值、其余模数（点）处取 0 的基。
Shamir \((t,n)\) 门限方案将秘密 \(s\) 拆给 \(n\) 方，使得任意 \(t\) 方能重建 \(s\)，而任意 \(\le t-1\) 方得不到任何信息。取素数 \(p>n\)，在 \(\mathrm{GF}(p)\) 上操作。
分发者随机选取次数 \(\le t-1\) 的多项式 \(P(x)=s+c_1x+\cdots+c_{t-1}x^{t-1}\)，系数 \(c_i\) 独立均匀随机。向第 \(i\) 方发送份额 \((i,P(i))\)。
重建：任意 \(t\) 方把他们持有的 \(t\) 个不同点代入 Lagrange 插值，唯一确定 \(P\)，再计算 \(P(0)=s\)。
完美保密性：设攻击者持有 \(t-1\) 个份额 \((x_i,y_i)\)。对任意候选秘密 \(s'\in\mathrm{GF}(p)\)，存在唯一一个次数 \(\le t-1\) 的多项式经过这 \(t-1\) 个点与 \((0,s')\)（由插值唯一性）。由于分发者最初对各系数均匀随机选取，所有 \(s'\) 先验与后验概率相等，攻击者无法缩小秘密范围。
扩展：访问结构可分层实现。例如"unanimity（某类全部出席）AND multi-class（至少两类出席）"可拆成两个独立秘密 \(U,M\) 分别共享，再用一个一次多项式 \(R\) 满足 \(R(0)=s,R(1)=M,R(2)=U\)，仅当 \(U,M\) 均被恢复时才能解出 \(s\)。委托（delegation）则通过"共享一个份额"实现：把每国份额再用一个低次多项式分给该国代表。
在 \(\mathrm{GF}(11)\) 上构造 \((3,5)\)-门限方案分享秘密 \(s=7\)。选取 \(P(x)=7+3x+2x^2\pmod{11}\)。
计算份额：\(P(1)=7+3+2\equiv 1\)，\(P(2)=7+6+8\equiv 10\)，\(P(3)=7+9+18\equiv 1\)，\(P(4)=7+12+32\equiv 7\)，\(P(5)=7+15+50\equiv 6\)。分别发送给五方。
重建（第 1,2,3 方合作）：持有 \((1,1),(2,10),(3,1)\)。Lagrange 插值（利用 \(2^{-1}\equiv 6\pmod{11}\)）给出唯一二次多项式 \(P(x)\equiv 2x^2+3x+7\pmod{11}\)，从而 \(P(0)=7=s\)。若仅两方合作，则对每个 \(s'\in\mathrm{GF}(11)\) 都存在兼容的二次多项式，秘密完全不确定。
纠错码把长度为 \(n\) 的消息编码为次数 \(\le n-1\) 的多项式 \(P\) 在若干点上的取值并发送。根据错误类型，冗余需求截然不同。
擦除错误指接收方知道哪些包丢失（位置已知）。为防护至多 \(k\) 次丢失，发送 \(n+k\) 个包；接收方至少收到 \(n\) 个正确点，插值即可还原 \(n\) 个未知系数。这里冗余量是 \(k\)。
一般错误指某些包的值被篡改但接收方不知位置。Berlekamp-Welch 算法证明发送 \(n+2k\) 个包可防护至多 \(k\) 个一般错误。代价翻倍的原因在于需要同时定位错误（\(k\) 个未知位置）并纠正它们，反映为错误定位多项式与 \(Q\) 多项式的额外自由度。
分数错误模型：设发送 \(m\) 个包，至多 \(\alpha m\) 个出错（\(0<\alpha<1\)）。擦除情形需 \((1-\alpha)m\ge n\)，即 \(m\ge n/(1-\alpha)\)。一般错误情形需 \(m=n+2k\) 且 \(k\ge\alpha m\)，得 \(m\ge n/(1-2\alpha)\)；当 \(\alpha\ge 1/2\) 时分母非正，恢复不可能——直觉上一半以上被篡改时无法区分信号与噪声。
消息长度 \(n=6\)，运算在 \(\mathrm{GF}(13)\) 上。防护 \(k=2\) 次擦除需发送 \(n+k=8\) 个包；防护 \(k=2\) 个一般错误需发送 \(n+2k=10\) 个包。
分数情形：\(n=12\)，\(\alpha=1/4\)。擦除至少需 \(m\ge 12/(1-1/4)=16\) 个包；一般错误至少需 \(m\ge 12/(1-1/2)=24\) 个包。若一般错误比例达到 \(\alpha=1/2\)，则 \(1-2\alpha=0\)，无法保证恢复。
Berlekamp-Welch 算法防护 \(k\) 个一般错误。发送方把长度 \(n\) 的消息编码为次数 \(\le n-1\) 的多项式 \(P\)，并发送 \(n+2k\) 个取值 \(P(0),\ldots,P(n+2k-1)\)。接收方收到 \(r_0,\ldots,r_{n+2k-1}\)，其中至多有 \(k\) 个位置满足 \(r_i\neq P(i)\)。
引入首一错误定位多项式 \(E(x)=\prod_{j\in\mathcal{E}}(x-j)\)，其中 \(\mathcal{E}\) 是未知的错误位置集合，\(|\mathcal{E}|\le k\)。若位置 \(i\) 出错则 \(E(i)=0\)。再定义 \(Q(x)=P(x)E(x)\)，则 \(\deg Q\le (n-1)+k=n+k-1\)。核心恒等式：对每个 \(i\) 都有 \(Q(i)=r_i\cdot E(i)\)。若 \(i\) 未出错，\(P(i)=r_i\) 直接推出等式；若 \(i\) 出错，\(E(i)=0\) 使两边皆为零。
未知量计数：\(Q\) 有 \(n+k\) 个系数（次数 \(\le n+k-1\)），\(E\) 有 \(k\) 个自由系数（首一，次数 \(\le k\)），合计 \(n+2k\) 个未知量，恰好等于方程个数。对此线性方程组高斯消元可得一组 \((Q,E)\)。
还原：多项式除法 \(P(x)=Q(x)/E(x)\)（\(E\) 整除 \(Q\)）。若实际错误少于 \(k\) 个，方程组可能有多组解 \((Q,E)\)，但商 \(P=Q/E\) 唯一：对任意两组解，\(Q'E=QE'\) 作为多项式成立（它们作为函数在 \(n+2k\) 点相等且次数 \(\le n+2k-1\)），故商相同。
在 \(\mathrm{GF}(11)\) 上发送长度 \(n=2\) 的消息，防护 \(k=1\) 个一般错误。取 \(P(x)=3x+5\)，发送 \(n+2k=4\) 个包：\(P(0)=5,P(1)=8,P(2)=0,P(3)=3\)。
设位置 2 被篡改，接收向量 \(r=(5,8,4,3)\)。设 \(E(x)=x+e_0\)（首一一次），\(Q(x)=q_2x^2+q_1x+q_0\)（次数 \(\le 2\)）。由 \(Q(i)=r_iE(i)\) 得方程组（模 11）：\(q_0=5e_0\)，\(q_2+q_1+q_0=8(1+e_0)\)，\(4q_2+2q_1+q_0=4(2+e_0)\)，\(9q_2+3q_1+q_0=3(3+e_0)\)。
高斯消元解得 \(e_0=9\)，即 \(E(x)=x+9\equiv x-2\)，其根 \(x=2\) 正是出错位置；以及 \(Q(x)=3x^2+10x+1\)。多项式除法 \(Q/E\)：\((3x^2+10x+1)=(x+9)(3x+5)\)，故 \(P(x)=3x+5\)，完全恢复原始消息。若实际无错，方程组虽有多组 \((Q,E)\) 解，但商仍为同一 \(P\)。
错误。有限域上的函数环存在零因子，例如 p=2 时 f(x)=1+x 与 g(x)=x 均非零，但乘积在 GF(2) 的每一点都为零。这与实数域上非零多项式只有有限个根不同。
不准确。d+1 个点唯一确定的是次数 ≤d 的多项式；若要求次数恰好为 d，则存在无穷多个更高次多项式也经过这些点（再加上任意倍的 ∏(x−x_i)）。
恰好相反：v·n_2=1−u·n_1 在模 n_1 下为 1、模 n_2 下为 0；u·n_1 在模 n_1 下为 0、模 n_2 下为 1。这是 CRT 构造基解的关键方向。
在有限域 GF(p) 上并非如此：对任意候选秘密 s'，都恰好存在一个次数 ≤t−1 的多项式经过已知 t−1 个点与 (0,s')，因此所有候选等可能，方案具有完美保密性。
错误。错误定位多项式 E(x) 的根就是出错位置，但它是待求解的未知量之一；接收方只建立 Q(i)=r_iE(i) 的线性方程组，通过求解同时得到 E 与 Q。
问题：有限域 \(\mathrm{GF}(p)\) 上，一个非零多项式的次数为 \(d\)，则它最多有多少个根？
问题：中国剩余定理中，若 \(n_1,n_2\) 互素且 \(u n_1+v n_2=1\)，则 \(v n_2\) 满足什么同余条件？
问题：在 Shamir \((t,n)\) 门限方案中，攻击者收买 \(t-1\) 个参与者后能获得关于秘密的什么信息？
问题：要发送长度为 \(n\) 的消息并防护最多 \(k\) 个一般错误，Berlekamp–Welch 编码需要发送多少个包？
cs70-cheatsheet.pdf · Note 8 · confidence: high · a nonzero polynomial of degree d has at most d rootsdiscussion/dis04b.pdf · 2 · confidence: high · Find a unique polynomial p(x) of degree at most 3 that passes through points...using the Lagrange interpolationhomework/hw05.pdf · 3 · confidence: high · all solutions are equivalent (mod n1n2···nk)homework/hw05.pdf · 3(d) · confidence: high · The CRT then establishes the existence of p(x)...p(x) is unique if its degree is at most k−1. Lagrange interpolation finds p(x).cs70-cheatsheet.pdf · Note 8 · confidence: high · 2 points uniquely determine a line; given t+1 pairs (xi,yi)...get the secretdiscussion/dis05a.pdf · 1 · confidence: high · We send n + 2k packets for k general errors. 与 We can compute P(x) using the equation: P(x) = Q(x)/E(x).