Lecture 7: Polynomials（多项式）

目录 · ← l7 · l9 →

Lecture 7: Polynomials（多项式）

概述

前六讲我们处理的都是单个数字的模算术：$x$ 的逆元、$a^{p-1} \bmod p$、$N = pq$ 的分解。本讲把视角抬高一维——研究函数：多项式 (polynomial)。核心问题是：一个多项式有多少个根？需要多少个点的取值才能把它完全钉死？

答案是两个极其简洁的定理：次数为 $d$ 的非零多项式最多有 $d$ 个根，以及$d+1$ 个横坐标互不相同的点唯一确定一个次数不超过 $d$ 的多项式。第二定理的构造性证明叫拉格朗日插值 (Lagrange interpolation)。

真正让这两个定理”活”起来的，是把它搬到有限域 (finite field) $\mathbb{F}_p$ 上。在实数上这些性质早就熟悉；但在只有 $p$ 个元素的有限域上，同样的代数结论竟然原封不动地成立——这一”神奇事实”是下一讲秘密共享 (secret sharing) 与纠错码 (error-correcting codes) 的全部基础。

本讲最容易踩的两个坑是：（1）在 $\mathbb{Z}_m$ 上 $m$ 不是质数时，两个定理全都失效（例如模 8 下 $x^3$ 有 4 个根）；（2）在 $\mathbb{F}_p$ 上，多项式函数与多项式不是一回事：$x^p$ 与 $x$ 作为函数完全相同，但作为多项式不同。次数不超过 $p-1$ 时两者才一一对应。

核心概念的直观解释

多项式 (polynomial) 与次数 (degree)

• 定义：单变量多项式是形如 \(p(x) = a_d x^d + a_{d-1}x^{d-1} + \cdots + a_1 x + a_0\) 的表达式，其中系数 (coefficients) $a_i$ 取自某个数系（实数、有理数、复数，或本讲重点 $\mathbb{F}_p$）。若 $a_d \ne 0$，则称 $p$ 的次数 (degree) 为 $d$，记 $\deg p = d$，$a_d$ 称为首项系数 (leading coefficient)。零多项式 $p(x) \equiv 0$ 的次数不做定义（或约定为 $-\infty$），这是后面几个定理都要单独排除它的原因。
• 直观解释（”它是什么意思？”）：多项式是”最听话的函数“。它由一个有限的信息清单完全决定——只要给我那 $d+1$ 个系数，我就能算出它在任意输入上的取值，无论输入是 0、1000 还是 $10^{100}$。更惊人的是反过来：只要给我有限个点的取值（具体说是 $d+1$ 个），我也能反推出整个系数清单。对比一下：一个任意的函数 $f:\mathbb{R}\to\mathbb{R}$ 需要无穷多条信息才能描述；而多项式只需要 $d+1$ 个数字。这就是下一讲秘密共享的立足点——把秘密编码成多项式的一个系数，然后只分发点。
• 具体示例：$p(x) = 5x^3 + 2x + 1$。它的次数 $d = 3$，系数为 $a_3 = 5$，$a_2 = 0$，$a_1 = 2$，$a_0 = 1$。注意缺失的项系数为 0，”次数是 3”并不意味着 3 个系数都非零。这个元素在 $x = 2$ 处的取值是 $5 \cdot 8 + 2 \cdot 2 + 1 = 45$。

根 (root)

• 定义：$a$ 是 $p(x)$ 的根，如果 $p(a) = 0$。
• 直观解释：根就是曲线与 $x$ 轴的交点。$d$ 次曲线可以上下起伏很多次，但它只有 $d$ 次机会穿过 $x$ 轴——除非它压根就是零多项式 $y=0$（那条与 $x$ 轴重合的直线，有无穷多个”根”）。这正是”非零”这个条件不可省的原因。
• 具体示例：$p(x) = x^2 - 4$ 是 2 次多项式，根是 $2$ 与 $-2$，正好 2 个，达到上界。$q(x) = x^2 + 1$ 在 $\mathbb{R}$ 上一个根都没有（上界不紧，定理只说”最多”，没说”恰好”）。但在 $\mathbb{F}_5$ 上，$q$ 有根 $2$ 和 $3$（因为 $2^2 + 1 = 5 \equiv 0$，$3^2 + 1 = 10 \equiv 0$）——同一个多项式在不同域上的根完全不同，这是本讲反复出现的重要现象。

多项式相等：两种截然不同的含义

• 定义：系数意义下的相等：两个多项式相等，当且仅当逐项系数相等（同次项系数全同）。函数意义下的相等：两个多项式相等，当且仅当对定义域中每一个 $x$ 都有相同的取值。在 $\mathbb{R}$ 上，这两种含义恰好等价。在有限域 $\mathbb{F}_p$ 上，它们不等价。
• 直观解释：这是本讲最重要的观念分水岭。在 $\mathbb{R}$ 上定义域有无穷多个元素，”处处相同”是很难满足的条件；在 $\mathbb{F}_p$ 上定义域只有 $p$ 个元素，”处处相同”只是 $p$ 个等式——弱得多。所以函数相等只能”压住”那些被 $p$ 个点全部覆盖掉的多项式。
• 具体示例：在 $\mathbb{F}_7$ 上，把 $x = 0,1,\ldots,6$ 全代进去，$x^7$ 与 $x$ 的取值分别是 $0,1,2,3,4,5,6$ 与 $0,1,2,3,4,5,6$——完全一样（这正是费马小定理的推论）。但 $x^7$ 的次数是 7 而 $x$ 的次数是 1，作为多项式它们显然不同。$x^7 - x$ 是 $\mathbb{F}_7$ 上次数为 7 但有 7 个根的多项式，恰好触到上界（且说明了为什么上界必须是 $d$ 而不是 $p-1$）。

有限域 (finite field) $\mathbb{F}_p$

• 定义：设 $m$ 为正整数。我们说在 $\mathbb{Z}_m$ 上”能做域运算”，如果加、减、乘、除（除零以外）全都封闭。这成立当且仅当 $m$ 是质数。此时记作 $\mathbb{F}_m$ 或 $GF(m)$（Galois Field，伽罗瓦域）。域 (field) 是一组满足特定公理的集合，这些公理正是让多项式性质成立的全部基础。
• 直观解释：多项式理论的所有证明只用到一件事：你能对任意两个元素做加减乘除，只要不除以零。所以真正需要的不是”实数”这个具体数系，而是”能做四则运算”这个抽象结构。$\mathbb{R}$、$\mathbb{Q}$、$\mathbb{C}$ 都满足；$\mathbb{Z}_p$（$p$ 质数）也满足，因为讲次 4/5 已证 $\mathbb{Z}_p$ 中每个非零元都有乘法逆元。但 $\mathbb{Z}_8$ 不满足——$2$ 没有逆元——于是所有定理立即崩塌。
• 具体示例：$\mathbb{F}_5$ 上的除法：要算 $\frac{3}{2}$，先求 $2^{-1} \bmod 5 = 3$（因为 $2 \times 3 = 6 \equiv 1$），所以 $\frac{3}{2} = 3 \times 3 = 9 \equiv 4 \pmod 5$。验算：$2 \times 4 = 8 \equiv 3$ ✔。在 $\mathbb{F}_7$ 上 $\frac{1}{2} = 4$（$2 \times 4 = 8 \equiv 1$），$\frac{1}{-1} = -1 \equiv 6$。

系数表示与取值表示

• 定义：用 $d+1$ 个系数 $(a_0, a_1, \ldots, a_d)$ 来指定一个次数不超过 $d$ 的多项式，叫系数表示 (coefficient representation)；用它在 $d+1$ 个点上的取值 $(y_0, y_1, \ldots, y_d)$（对应 $x = 0, 1, \ldots, d$）来指定，叫取值表示 (value representation)。
• 直观解释：同一个对象的两套”坐标系”。系数表示适合做加法、乘法、求导；取值表示适合做逐点运算（想算 $p \cdot q$ 在某点的值？直接两个值相乘即可，不用展开多项式）。两者之间的转换：系数 → 取值靠代入求值（$O(d^2)$ 或更快）；取值 → 系数靠拉格朗日插值。这正是下一讲里”分享秘密 / 恢复秘密”两步的代数形式。
• 具体示例：$\mathbb{F}_7$ 上次数不超过 2 的多项式共 $7^3 = 343$ 个（3 个系数各 7 种取值），由在 $x = 0,1,2$ 三点的取值也恰好是 $7^3 = 343$ 种可能。两套表示的数量一致，暗示了它们之间存在一一对应——这就是插值定理的计数版”预告”。

拉格朗日基多项式 (Lagrange basis polynomial)

• 定义：给定两两不同的 $x_1, \ldots, x_{d+1}$，定义 \(\Delta_i(x) = \prod_{j \ne i} \frac{x - x_j}{x_i - x_j}.\)
• 直观解释：$\Delta_i$ 是一个”开关函数“（在数学上叫指示函数）：它在 $x_i$ 处取 $1$，在所有其他 $x_j$（$j \ne i$）处取 $0$。想构造一个在点 $x_i$ 上取指定值 $y_i$ 的多项式？只要把开关 $\Delta_i$ 乘以 $y_i$ 再加起来。这些开关只依赖于 $x_1,\ldots,x_{d+1}$ 的位置，与目标值 $y_i$ 完全无关——所以可以事先把开关造好，反复使用。这和 CRT 中的”基向量” $b_i$（在方向 $i$ 上取 1、其他方向取 0）是同一个思想。
• 具体示例：取 $x_1 = 1, x_2 = 2, x_3 = 3$（$d+1 = 3$）。则 \(\Delta_2(x) = \frac{(x-1)(x-3)}{(2-1)(2-3)} = \frac{(x-1)(x-3)}{-1} = -(x-1)(x-3) = -x^2 + 4x - 3.\) 代入检验：$\Delta_2(1) = -1 + 4 - 3 = 0$ ✔，$\Delta_2(2) = -4 + 8 - 3 = 1$ ✔，$\Delta_2(3) = -9 + 12 - 3 = 0$ ✔。

完整证明与推导（核心）

定理 7.1（多项式除法定理 / Polynomial Division）：设 $p(x)$ 是次数为 $d$ 的多项式，$q(x)$ 是次数 $\le d$ 的多项式且 $q \not\equiv 0$。则存在唯一的多项式对 $(q^{\prime}(x), r(x))$ 使得

$q^{\prime}$ 称为商 (quotient)，$r$ 称为余式 (remainder)。

证明策略：这是一个构造性证明——用长除法（小学竖式除法的多项式版本）显式地把 $q^{\prime}$ 与 $r$ 造出来，再论证唯一性。构造过程每一步都消掉当前最高次项，所以必然终止。

逐步推导（先看一个完整的算例）：

用 $p(x) = x^3 + x^2 - 1$ 除以 $q(x) = x - 1$。

第 1 步：$p$ 的最高次项是 $x^3$，$q$ 的最高次项是 $x$。商里要放 $x^2$，因为 $x^2 \cdot (x-1) = x^3 - x^2$。

第 2 步：剩 $2x^2 - 1$，最高次项 $2x^2$。商里放 $2x$，因为 $2x(x-1) = 2x^2 - 2x$。

第 3 步：剩 $2x - 1$，最高次项 $2x$。商里放 $2$，因为 $2(x-1) = 2x - 2$。

第 4 步：剩余的 $1$ 的次数 $0 < \deg q = 1$，停止。

把三步合并：

所以商 $q^{\prime}(x) = x^2 + 2x + 2$，余式 $r(x) = 1$。

验算：$(x^2 + 2x + 2)(x - 1) = x^3 + 2x^2 + 2x - x^2 - 2x - 2 = x^3 + x^2 - 2$，再加 $1$ 得 $x^3 + x^2 - 1$ ✔。

用熟悉的竖式写法：

          X^2 + 2X + 2        <- 商 q'(x)
        ┌─────────────────────
  X - 1 │ X^3 + X^2 + 0X - 1  <- 被除数 p(x)（补上缺失的 0X 项）
          X^3 - X^2             <- 减去 X^2·(X-1)
          ─────────
                2X^2 + 0X       <- 差 2X^2 - 1 的 0X 是占位
                2X^2 - 2X       <- 减去 2X·(X-1)
                ─────────
                       2X - 1   <- 差
                       2X - 2   <- 减去 2·(X-1)
                       ──────
                            1   <- 余式 r(x) = 1，次数 0 < 1

一般情形的构造：初始化 $r \leftarrow p$，$q^{\prime} \leftarrow 0$。只要 $\deg r \ge \deg q$，设 $r$ 的首项为 $c x^e$（$e = \deg r$）、$q$ 的首项为 $b x^f$（$f = \deg q \le e$）。令单项式 $t(x) = \frac{c}{b} x^{e-f}$（$\frac{c}{b}$ 在域中存在，因为 $b \ne 0$），做

这样 $r$ 的 $x^e$ 项被精确消成 $0$，所以新的 $\deg r < e$，严格下降。因为次数是非负整数，过程必然在有限步后使 $\deg r < \deg q$ 而终止。

唯一性：设 $p = q_1^{\prime} q + r_1 = q_2^{\prime} q + r_2$，其中 $\deg r_1, \deg r_2 < \deg q$。相减得

若 $q_1^{\prime} \ne q_2^{\prime}$，则左边是次数 $\ge \deg q$ 的非零多项式（域上多项式乘积的次数等于次数之和，因为首项系数之积不为零）；而右边次数 $< \deg q$。矛盾。故 $q_1^{\prime} = q_2^{\prime}$，进而 $r_1 = r_2$。$\blacksquare$

【证明机制解说】：关键在于域这个条件——每一步都要除以 $q$ 的首项系数 $b$，这要求 $b$ 可逆。在 $\mathbb{Z}_8$ 上除不尽就会卡住（比如试图用 $2x+1$ 除 $x^2$ 时系数 $\frac{1}{2}$ 不存在）。第二个关键是次数严格下降这个”进度度量”，它保证构造终止——和讲次 5 中欧几里得算法的”余数严格变小”是同一个套路。

定理 7.2（因式定理 / Factor Theorem）：设 $P(x)$ 为多项式，$r$ 为常数。则

证明策略：双向证明（等价命题要证两个方向）。充分性（$\Leftarrow$）用定理 7.1 的带余除法：除以 $x - r$ 得到的余式次数 $< 1$，所以是常数 $c$，再把 $x = r$ 代进去求出 $c$。必要性（$\Rightarrow$）直接代入。

逐步推导：

($\Rightarrow$) 设 $(x-r) \mid P(x)$，即存在多项式 $Q$ 使 $P(x) = (x-r)Q(x)$。代入 $x = r$：

($\Leftarrow$) 设 $P(r) = 0$。用 $x - r$（次数 1，$\le \deg P$）作除数，由定理 7.1 存在商 $Q$ 与余式 $R$ 使

$\deg R < 1$ 意味着 $R$ 是常数，记 $R(x) = c$。代入 $x = r$：

由假设 $P(r) = 0$ 得 $c = 0$，即 $R \equiv 0$。于是 $P(x) = (x-r)Q(x)$，即 $(x-r) \mid P(x)$。$\blacksquare$

若 $P$ 的次数为 $d \ge 1$ 且首项系数为 $a_d$，则由 $P = (x-r)Q$ 比较首项系数知 $Q$ 的次数恰为 $d - 1$、首项系数为 $a_d$。

【证明机制解说】：这个引理是根定理的发动机。它把”求值等于零”（一个数值事实）翻译成”有一个线性因子”（一个代数结构事实）。有了这个翻译，我们就可以反复提取因子：每找到一个根就砍掉一次次数。这正是下面定理 7.3 归纳证明的机制。

反例（在非域上定理失效）：定理 7.2 的证明依赖定理 7.1 的带余除法，而带余除法在 $\mathbb{Z}_m$（$m$ 非质数）上可能失败。取 $m = 8$，$P(x) = x^3$，$r = 2$。$P(2) = 8 \equiv 0 \pmod 8$，所以 $2$ 是根。但是否有 $(x - 2) \mid x^3$ 在 $\mathbb{Z}_8[x]$ 中？若 $x^3 = (x-2)Q(x)$，则 $Q$ 必须是次数 2 的多项式 $ax^2+bx+c$。展开得 $ax^3 + (b - 2a)x^2 + (c-2b)x - 2c$。比较系数：$a = 1$；$b - 2a = 0 \Rightarrow b = 2$；$c - 2b = 0 \Rightarrow c = 4$；最后 $-2c = -8 \equiv 0 \pmod 8$ ✔ 竟然成立。所以这次因式分解碰巧还能做——但下面的反例会说明在 $\mathbb{Z}_8$ 上根定理整体崩掉。

定理 7.3（有限根定理 / Degree-Root Bound）：设 $\mathbb{F}$ 为任意域（$\mathbb{R}$、$\mathbb{Q}$、$\mathbb{C}$ 或 $\mathbb{F}_p$），$P(x)$ 是 $\mathbb{F}$ 上非零的、次数为 $d$ 的多项式。则 $P$ 在 $\mathbb{F}$ 中最多有 $d$ 个根。

证明策略：对次数 $d$ 做（弱）归纳。为了把归纳跑起来，先证一个辅助命题（Claim A）说明”差不多取到上界”的多项式能完全因式分解；然后用它推出根数的上界。

逐步推导：

Claim A：若 $P(x)$ 是次数为 $d \ge 1$ 的多项式，且 $a_1, \ldots, a_d$ 是 $P$ 的 $d$ 个两两不同的根，则存在常数 $c \ne 0$ 使

Claim A 的证明（对 $d$ 归纳）：

• 基础情形 $d = 1$：$P(x) = a_1^{\prime} x + a_0$ 且 $a_1^{\prime} \ne 0$。设 $a_1$ 是它的根，则 $0 = P(a_1) = a_1^{\prime} a_1 + a_0$，所以 $a_0 = -a_1^{\prime} a_1$，于是 $P(x) = a_1^{\prime} x - a_1^{\prime} a_1 = a_1^{\prime}(x - a_1)$，即 $c = a_1^{\prime} \ne 0$ 的形式。✔

  （若约定基础情形为 $d = 0$：次数为 0 的多项式是常数 $c \ne 0$，它没有根，Claim A 的前提”有 $d = 0$ 个不同根”平凡满足，而 $P = c$ 正是空乘积形式。两种约定都可以，下面用 $d \ge 1$ 的版本，更直观。）

• 归纳假设：对某个 $d \ge 1$，任何次数为 $d$、有 $d$ 个不同根的多项式都能写成首项系数乘以全体线性因子之积。

• 归纳步骤：设 $P$ 次数为 $d+1$，有 $d+1$ 个两两不同的根 $a_1, \ldots, a_{d+1}$。取 $a_{d+1}$：由因式定理（定理 7.2），$P(x) = (x - a_{d+1}) Q(x)$，其中 $Q$ 的次数为 $(d+1) - 1 = d$。

  现在证明 $a_1, \ldots, a_d$ 都是 $Q$ 的根。对每个 $i \le d$：

  \[0 = P(a_i) = (a_i - a_{d+1}) Q(a_i).\]

  因为各根两两不同，$a_i \ne a_{d+1}$，所以 $a_i - a_{d+1} \ne 0$。在域中非零元可逆，两边乘 $(a_i - a_{d+1})^{-1}$ 得 $Q(a_i) = 0$。✔

  于是 $Q$ 是次数为 $d$ 的多项式，有 $d$ 个两两不同的根 $a_1, \ldots, a_d$。由归纳假设，$Q(x) = c(x - a_1)\cdots(x - a_d)$，其中 $c$ 是 $Q$ 的首项系数（非零）。代回：

  \[P(x) = (x - a_{d+1}) \cdot c(x-a_1)\cdots(x-a_d) = c(x-a_1)\cdots(x-a_d)(x-a_{d+1}). \qquad \checkmark\]

由 Claim A 推出定理 7.3：Claim A 处理的是”恰好 $d$ 个根”的情形，而定理 7.3 要处理的是”任意多个根”的一般情形，所以不能直接套用。下面改用因式定理 + 对次数归纳，这是最顺的路径。

对 $d$ 归纳证明”次数为 $d$ 的非零多项式至多有 $d$ 个根”。

• 基础情形 $d = 0$：非零常数 $c$ 处处不为零，根数 $= 0 \le 0$。✔
• 归纳假设：次数为 $d$ 的非零多项式至多有 $d$ 个根。

• 归纳步骤：设 $P$ 次数为 $d+1$。若 $P$ 无根，根数 $0 \le d+1$ ✔。否则取一个根 $r$，由因式定理 $P(x) = (x-r)Q(x)$，$\deg Q = d$。

  设 $a$ 是 $P$ 的任意根，即 $0 = P(a) = (a-r)Q(a)$。因为域中没有零因子（$uv = 0 \Rightarrow u = 0$ 或 $v=0$；等价说法：非零元可逆），所以 $a = r$ 或 $Q(a) = 0$。

  因此 $P$ 的根集 $\subseteq \{r\} \cup \{Q \text{ 的根}\}$。由归纳假设 $Q$ 至多有 $d$ 个根，所以 $P$ 的根数至多 $d + 1 = \deg P$。$\blacksquare$

【证明机制解说】：整个证明的支点是域没有零因子这一条性质：$(a-r)Q(a) = 0$ 时必有一边为零。在 $\mathbb{Z}_8$ 上这句话就假了——$2 \cdot 4 = 8 \equiv 0$，而 $2 \ne 0$、$4 \ne 0$。这一个漏洞会让整座大厦倒塌（见下面的反例）。另一处同样重要的是归纳假设的用法：从 $P$ 剥掉一个线性因子，得到一个次数更小、根更少的 $Q$，把问题交给归纳假设。

反例 7.4（在非域 $\mathbb{Z}_8$ 上根定理彻底失效）

在 $\mathbb{Z}_8$ 上看 $P(x) = x^3$。它的次数是 3，按定理 7.3 应有至多 3 个根。实际检查 $x = 0,1,\ldots,7$：

4 个根：$\{0, 2, 4, 6\}$。这比次数 3 还多，直接违反定理 7.3；插值定理（定理 7.6）也随之失效（存在性、唯一性都不成立）。

根因：$\mathbb{Z}_8$ 中 $2 \cdot 4 = 8 \equiv 0$，存在零因子 (zero divisor)。无法在 $\mathbb{Z}_8$ 里补出一个”域”来救这个定理——虽然确实存在含 8 个元素的域，但它不是 $\mathbb{Z}_8$，而是一个更复杂的构造（$\mathbb{F}_2$ 上的一次扩域）。这说明 $p$ 为质数这个条件是本质的，不是技术上的便利。

反例 7.5（根定理的上界不可放宽）

在 $\mathbb{F}_7$ 上取 $P(x) = x(x-1)(x-2) = x^3 - 3x^2 + 2x$，次数 $d = 3$。代入得根 $\{0, 1, 2\}$，恰好 3 个，正好触到上界——所以”至多 $d$ 个”不能改进为”至多 $d-1$ 个”。

更极端的是 $P(x) = x^7 - x$ 在 $\mathbb{F}_7$ 上。对 $x = 0,1,\ldots,6$，由费马小定理 $x^7 \equiv x \pmod 7$，所以 $P(x) \equiv 0$ 对全部 7 个元素成立，即有 7 个根。而 $\deg(x^7-x) = 7$，上界 $d = 7$ 依然成立——这个例子恰好说明了为什么上界的形式是 $d$ 而不是 $p-1$。

下面这张图直观地对比了”在 $\mathbb{R}$ 上”与”在 $\mathbb{F}_7$ 上”同一个次数上界的含义：

   （A）实数域 R 上：d 次曲线的"根"= 与 x 轴的交点，至多 d 个
        P(x) = (1/2)x^2 - (1/2)x + 1        （算例 A 的结果）
          y
          |        *                      * = 数据点 (1,1),(2,2),(3,4)
        4 |                 ●
          |              ／   ＼
        2 |      ●     ／         ＼
          |    ／   ＼／              ＼
        1 ●───       ●                 ＼
          └───┬───┬───┬───┬───┬───┬──► x
              1   2   3   4   5   6
        P(4) = 7（插值外推）；在 R 上 P 无实根（判别式 1-8 = -7 < 0）

   （B）有限域 F_7 上：定义域只有 7 个孤立点，"曲线"退化成 7 个孤立坐标
        P(x) = 4x^2 + 3x + 1              （算例 B：同一个三点表的 F_7 版本）
          y
        6 |
        5 |
        4 |        ●               ●          ● = 非零取值
        3 |
        2 |            ●                   ●
        1 | ●      ●
        0 |____________________________○_______  x
            0   1   2   3   4   5   6
           P 的取值表：( 1,  1,  2,  4,  0,  4,  2 )
                        ↑   ↑               ↑
                      x=0  x=1           x=4 ← 唯一的根
        ○ = 根 P(4) = 4·16 + 3·4 + 1 = 77 ≡ 77 - 77 = 0 (mod 7)
        注意：同一个多项式在 R 上（算例 A）判别式 1-8 = -7 < 0，一个实根都没有；
              在 F_7 上却有一个根 x = 4。数根必须指明"在哪个域中数"。

   （C）根个数与次数的关系（F_7，次数 d ≤ 6）
        d 次非零多项式：最多 d 个根        ← 定理 7.3
        x(x-1)(x-2) : d=3, 根={0,1,2}      恰 3 个 = 上界（紧）
        x^7 - x     : d=7, 根={0,1,...,6}   恰 7 个 = 上界（紧）
        x^2 + 1 在 F_5 上 : d=2, 根={2,3}   恰 2 个（对比：R 上 0 个根）
        x^3 在 Z_8 上     : d=3, 根={0,2,4,6}  4 个 > 3 ✗ 非域！

定理 7.6（插值定理 / Lagrange Interpolation）：给定 $d+1$ 对数据 \((x_1, y_1), (x_2, y_2), \ldots, (x_{d+1}, y_{d+1}),\) 其中 $x_1, \ldots, x_{d+1}$ 两两不同（都在同一个域 $\mathbb{F}$ 中），则存在唯一的一个次数不超过 $d$ 的多项式 $P(x)$ 满足 $P(x_i) = y_i$（$1 \le i \le d+1$）。

证明策略：存在性用构造性证明（把多项式显式写出来并验证），唯一性用反证法 + 根定理。选这个策略的理由是：存在性有一条非常干净的代数路径（基函数法），而唯一性几乎”免费”地由定理 7.3 得到。

逐步推导（第一部分：存在性）

第 1 步：先解一个”最简单的”特例。

假设目标取值是 $y_1 = 1$ 而 $y_2 = y_3 = \cdots = y_{d+1} = 0$。这时我们要的多项式是什么？观察

$x$ 出现了 $d$ 次，所以 $\deg q = d$ ✔。当 $j \ge 2$ 时，$q(x_j)$ 的乘积里含有因子 $(x_j - x_j) = 0$，所以 $q(x_j) = 0$ ✔。而

因为每个因子 $x_1 - x_j \ne 0$（$x_i$ 两两不同），而域中没有零因子。所以 $q(x_1)$ 可逆，我们可以把它”归一化”：

这满足 $P(x_1) = 1$ 与 $P(x_j) = 0$（$j \ge 2$）✔。

小算例：给定 $(1,1), (2,0), (3,0)$。则 $q(x) = (x-2)(x-3) = x^2 - 5x + 6$，$q(x_1) = q(1) = (1-2)(1-3) = 2$。所以 $P(x) = \frac{x^2 - 5x + 6}{2}$。检验：$P(1) = \frac{1 - 5 + 6}{2} = \frac{2}{2} = 1$ ✔，$P(2) = \frac{4 - 10 + 6}{2} = \frac{0}{2} = 0$ ✔，$P(3) = \frac{9 - 15 + 6}{2} = \frac{0}{2} = 0$ ✔。

第 2 步：把这个特例推广到任意一个指标 $i$。

把”第 1 个点取 1、其余取 0”换成”第 $i$ 个点取 1、其余取 0”，定义

分母 $\prod_{j\ne i}(x_i - x_j)$ 是非零常数（$x$ 一个都不出现，全由 $x_k$ 构成；且每个因子非零，无零因子故乘积非零），所以这个除法合法。由构造：

每个 $\Delta_i$ 的次数恰好是 $d$（分子是 $d$ 个一次因式之积）。这些 $\Delta_i$ 称为拉格朗日基多项式。

第 3 步：线性组合得到一般解。

验证：$P$ 是 $d+1$ 个次数 $\le d$ 的多项式之和，故 $\deg P \le d$ ✔。代入 $x = x_k$：

存在性证毕。

逐步推导（第二部分：唯一性）

反设存在另一个次数 $\le d$ 的多项式 $Q(x) \ne P(x)$ 满足 $Q(x_i) = y_i$ 对全部 $i$。考虑差

$R$ 是次数 $\le d$ 的多项式。因为 $P \ne Q$ 作为多项式不同，$R$ 不是零多项式（次数 $\le d$ 的多项式的系数逐一相减，不全为零）。于是 $R$ 有确定的次数 $\deg R = d^{\prime} \le d$。

另一方面，对每个 $i \in \{1, \ldots, d+1\}$：

所以 $R$ 有 $d+1$ 个两两不同的根 $x_1, \ldots, x_{d+1}$。

由定理 7.3（有限根定理），次数为 $d^{\prime} \le d$ 的非零多项式至多有 $d^{\prime} \le d$ 个根。但 $R$ 有 $d+1 > d \ge d^{\prime}$ 个根，矛盾。

所以不存在这样的 $Q$，$P$ 唯一。$\blacksquare$

【证明机制解说】：两个部分各有各的巧妙。

存在性的核心是”先解最简单的情形再线性叠加“。这个套路在数学里到处出现（CRT 的基向量、线性代数里”标准基 + 坐标”、傅里叶级数里的正交基）。拉格朗日基 $\Delta_i$ 就是”取值空间”里的一组标准基：$\Delta_i$ 是”第 $i$ 个坐标为 1、其余为 0”的单位向量。$P = \sum y_i \Delta_i$ 就是”以 $(y_1, \ldots, y_{d+1})$ 为坐标的线性组合”。注意 $\Delta_i$ 只依赖 $x_1,\ldots,x_{d+1}$，不依赖 $y_i$——所以可以预先造好基，之后任意调整系数即可。

唯一性的核心是”把两个候选解相减，得到一个根太多的小多项式“。$R$ 有 $d+1$ 个根但次数 $\le d$，违反根定理，故 $R$ 只能是零多项式——而零多项式就意味着 $P = Q$。这是一个标准的“反证 + 计数”论证：把”存在两个不同解”的假设转化成”存在一个违反已知界的对象”。

为什么这个定理如此重要：它说的恰是”$d+1$ 个点唯一确定一个 $d$ 次多项式”。认定这句话有三重含义：（i）信息量恰好匹配——$d+1$ 个点的取值（$d+1$ 个域元素）与 $d+1$ 个系数一一对应；（ii）任意 $d$ 个点都不够（有多个候选多项式），$d+1$ 个点就够（唯一）；（iii）这个”够与不够”的临界点正是下一讲Shamir 秘密共享的门限 $k$：分发 $n$ 份，任意 $k$ 份可恢复、任意 $k-1$ 份零信息。

完整手算插值算例 A（官方 Note 的算例，实数域）

求过 $(1,1), (2,2), (3,4)$ 的次数 $\le 2$ 多项式（$d = 2$，$d+1 = 3$ 个点）。

基多项式：

组合：

逐项累加（先按 $x^2, x^1, x^0$ 分组）：

• $x^2$ 项：$\frac{1}{2} + 2 \cdot (-1) + 4 \cdot \frac{1}{2} = \frac{1}{2} - 2 + 2 = \frac{1}{2}$
• $x^1$ 项：$-\frac{5}{2} + 2 \cdot 4 + 4 \cdot (-\frac{3}{2}) = -\frac{5}{2} + 8 - 6 = -\frac{1}{2}$
• $x^0$ 项：$3 + 2 \cdot (-3) + 4 \cdot 1 = 3 - 6 + 4 = 1$

验算：$P(1) = \frac{1}{2} - \frac{1}{2} + 1 = 1$ ✔；$P(2) = 2 - 1 + 1 = 2$ ✔；$P(3) = \frac{9}{2} - \frac{3}{2} + 1 = 3 + 1 = 4$ ✔。

顺带观察：$P(0) = 1$，$P(4) = 8 - 2 + 1 = 7$。插值把一个离散的三点表变成了可以预测第四点、第五点的连续模型——这正是”多项式是最听话的函数”的含义。

完整手算插值算例 B（同一组点的 $\mathbb{F}_7$ 版本）

仍然求过 $(1,1), (2,2), (3,4)$。注意这三个点在 $\mathbb{F}_7$ 中的横坐标互不相同，且 $4 < 7$，所以数据合法。

基多项式（除法 = 乘以逆元）：$\mathbb{F}_7$ 中 $2^{-1} = 4$（$2 \times 4 = 8 \equiv 1$），$(-1)^{-1} = 6$（$-1 \equiv 6$，$6 \times 6 = 36 \equiv 1$）。

（$-20 \equiv -20 + 21 = 1$，$24 \equiv 24 - 21 = 3$。）

（$-24 \equiv -24 + 28 = 4$，$18 \equiv 18 - 14 = 4$。）

（$-12 \equiv -12 + 14 = 2$，$8 \equiv 1$。）

组合：$P(x) = 1 \cdot \Delta_1 + 2 \cdot \Delta_2 + 4 \cdot \Delta_3$。

• $x^2$：$4 + 2\cdot 6 + 4 \cdot 4 = 4 + 12 + 16 = 32 \equiv 32 - 28 = 4$
• $x^1$：$1 + 2 \cdot 4 + 4 \cdot 2 = 1 + 8 + 8 = 17 \equiv 17 - 14 = 3$
• $x^0$：$3 + 2 \cdot 4 + 4 \cdot 1 = 3 + 8 + 4 = 15 \equiv 15 - 14 = 1$

验算：$P(1) = 4 + 3 + 1 = 8 \equiv 1$ ✔；$P(2) = 16 + 6 + 1 = 23 \equiv 23 - 21 = 2$ ✔；$P(3) = 36 + 9 + 1 = 46 \equiv 46 - 42 = 4$ ✔。在 $\mathbb{F}_7$ 上的完整取值表是 $(1, 1, 2, 4, 0, 4, 2)$——注意 $x = 4$ 处取 $0$，即 $4$ 是这个多项式在 $\mathbb{F}_7$ 上的根，而它在 $\mathbb{Q}$ 上的根是 $\frac{1 \pm \sqrt{-7}}{4}$（非有理数）。同一个”系数模式”的插值多项式在不同域上有完全不同的根结构。

完整手算插值算例 C（教科书式的三点算例，$(0,1),(1,2),(2,5)$）

$d = 2$，三个横坐标 $0, 1, 2$ 两两不同。

基多项式：分母分别是 $(0-1)(0-2) = 2$、$(1-0)(1-2) = -1$、$(2-0)(2-1) = 2$。

组合：

逐项展开：

按次合并：$x^2$ 项 $\frac{1}{2} - 2 + \frac{5}{2} = 1$；$x^1$ 项 $-\frac{3}{2} + 4 - \frac{5}{2} = 0$；$x^0$ 项 $\frac{2}{2} = 1$。所以

验算：$P(0) = 1$ ✔；$P(1) = 1 + 1 = 2$ ✔；$P(2) = 4 + 1 = 5$ ✔。$P(3) = 10$。

（重要提醒：这组数据常被误算成 $1 + \frac{1}{2}x + \frac{3}{2}x^2$——代入 $x=1$ 得 $1 + 0.5 + 1.5 = 3 \ne 2$，是错的。请务必自己代回原数据检验，这是插值题唯一可靠的验算方式。）

$\mathbb{F}_7$ 版本：$\mathbb{F}_7$ 中 $2^{-1} = 4$，$(-1)^{-1} = 6$。

（验算 $\Delta_2 = 6(x^2 - 2x) = 6x^2 - 12x \equiv 6x^2 + 2x$，减 $12 \equiv$ 加 $2$ ✔。）

（$36 \equiv 1$，$21 \equiv 0$ ✔。）在 $\mathbb{F}_7$ 上的完整取值表是 $(1, 2, 5, 3, 3, 5, 2)$，对 $x = 0,1,2$ 分别给出 $1,2,5$ ✔。

有限域上的多项式函数：不唯一的表示

在 $\mathbb{F}_p$ 上，一个”函数”$f: \mathbb{F}_p \to \mathbb{F}_p$ 可以用很多个不同的多项式来”实现”。最经典的例子是：由费马小定理，对每一个 $x \in \mathbb{F}_p$ 有

所以 $P(x) = x^p$ 与 $Q(x) = x$ 作为函数完全相同，但作为多项式不同（次数 $p$ vs $1$）。

那么什么时候函数与多项式一一对应？答案是加上次数限制：

命题 7.7：在 $\mathbb{F}_p$ 上，次数不超过 $p-1$ 的多项式与函数 $f: \mathbb{F}_p \to \mathbb{F}_p$ 之间存在一一对应。

证明：$\mathbb{F}p$ 中的元素是 $x_1 = 0, x_2 = 1, \ldots, x_p = p-1$，共 $p$ 个，两两不同。由插值定理 7.6（取 $d = p-1$，则 $d+1 = p$ 个点），任给一组函数值 $(y_0, \ldots, y{p-1})$ 存在唯一的次数 $\le p-1$ 的多项式取到这些值。而函数的个数是 $p^p$，次数 $\le p-1$ 的多项式的个数是 $p^p$（$p$ 个系数各 $p$ 种取值），两者相等，且映射满射 + 单射，故为双射。$\blacksquare$

推论：$\mathbb{F}_p$ 上任何函数 $f$ 都可以用唯一一个次数 $\le p-1$ 的多项式表示。而且任何次数 $\ge p$ 的多项式都可以通过反复减去 $c \cdot (x^p - x) x^m$ 来降低次数而不改变函数取值，最终归约到次数 $\le p-1$ 的唯一代表元。

具体示例（$\mathbb{F}_7$ 上）：$x^7 - x$ 作为函数恒为零，作为多项式次数为 7。更一般的例子：$P(x) = x^8 + 2x$ 在 $\mathbb{F}_7$ 上与哪个 $\le 6$ 次多项式相同？因为 $x^7 \equiv x$，所以 $x^8 = x \cdot x^7 \equiv x \cdot x = x^2$，于是 $P(x) \equiv x^2 + 2x \pmod 7$ 作为函数。次数从 8 降到 2。

Schwartz-Zippel 引理（有限域上多项式相等的概率界）

在 $\mathbb{F}_p$ 上，如果两个多项式 $P \ne Q$（作为多项式不同）但次数都不大，那么”随机取一个点恰好撞上它们相等”的概率很小。这就是 Schwartz-Zippel 引理：

引理 7.8（Schwartz-Zippel）：设 $\mathbb{F}$ 为域，$P, Q \in \mathbb{F}[x]$ 为两个不同的多项式，且 $\deg P, \deg Q \le d$。从 $\mathbb{F}$ 中均匀随机取一个元素 $r$，则

在 $\mathbb{F}_p$ 上即 $\Pr[P(r) = Q(r)] \le \frac{d}{p}$。

证明思路：令 $R(x) = P(x) - Q(x)$。因为 $P \ne Q$，$R$ 不是零多项式；又 $\deg R \le \max(\deg P, \deg Q) \le d$（实际次数记作 $d^{\prime} \le d$）。事件 “$P(r) = Q(r)$”恰好等价于 “$r$ 是 $R$ 的根”。

由有限根定理（定理 7.3），$R$ 在 $\mathbb{F}$ 中最多有 $d^{\prime}$ 个根。在有限域 $\mathbb{F}_p$ 上，$r$ 均匀分布在 $p$ 个元素中，每个元素被抽中的概率是 $\frac{1}{p}$。于是

具体示例一（$\mathbb{F}_5$）：取 $P(x) = x^2 + 1$，$Q(x) = x^2$，$d = 2$。$P - Q = 1$ 是常数，无根，所以 $\Pr[P(r) = Q(r)] = 0 \le \frac{2}{5}$ ✔（界不紧，但正确）。

取 $P(x) = x^2$，$Q(x) = 1$，$P - Q = x^2 - 1 = (x-1)(x+1)$。在 $\mathbb{F}_5$ 上根为 $x = 1$ 与 $x = 4$（因为 $-1 \equiv 4$），共 2 个。所以 $\Pr = \frac{2}{5}$，正好取到界 $\frac{d}{p} = \frac{2}{5}$ ✔（界的紧致性示例）。

具体示例二（$\mathbb{F}_7$，与算例 B 同一个多项式）：取 $P(x) = 4x^2 + 3x + 1$（算例 B 的结果），$Q(x) = x + 1$，$d = 2$。则 $P - Q = 4x^2 + 2x = 2x(2x + 1)$。在 $\mathbb{F}_7$ 上根为 $x = 0$ 与 $2x + 1 = 0$，即 $x = -2^{-1} = -4 \equiv 3$。共 2 个根，所以

恰好取到界 ✔。逐点核对：$P$ 在 $\mathbb{F}_7$ 上取值 $(1,1,2,4,0,4,2)$，$Q(x) = x+1$ 取值 $(1,2,3,4,5,6,0)$，在 $x = 0$（都取 1）与 $x = 3$（都取 4）处相等，其余处不等 ✔。

这个引理的用途：它是多项式恒等式检验 (polynomial identity testing) 的基础。若你想确认两个复杂表达式是否相等（比如判断某个电路实现是否正确），不必展开成系数；只需在随机点上求值。若结果不等，则必定不等；若结果相等，则它们很可能是同一个多项式——出错概率不超过 $d/p$。把 $p$ 取大就能把错误率压到任意小。这正是下一讲的 Berlekamp-Welch 纠错解码算法的思想源头。

与经典问题的联系

问题实际背景：门限秘密共享 (threshold secret sharing)

冷战时期，美国总统授权在极端紧急情况下使用核武器，以避免因无法及时与总统商议而延误反击。一个显然的治理要求是：不能让任何一个人单独掌握发射密码。设想政府规定，至少 $k > 1$ 名高级官员达成一致才能发起核打击。我们要设计一个方案，同时满足：

1. 任意 $k$ 名官员汇集各自的信息后可以算出密码并发动打击；
2. 任意 $k-1$ 名或更少的官员，即使把信息全部凑在一起也得不到密码的任何信息。注意这里说的”任何信息”非常强：他们不应知道密码是奇是偶、是不是质数、能否被某个数整除、甚至最低有效位是什么。

数学建模

设共有 $n$ 名官员，编号 $1$ 到 $n$，密码（秘密）是自然数 $s$。取一个大于 $n$ 且大于 $s$ 的质数 $q$，全程在 $\mathrm{GF}(q) = \mathbb{F}_q$ 上工作。（$\mathbb{F}_q$ 而不是 $\mathbb{R}$ 有两个关键好处：秘密的候选值有限，所以可以精确量化”零信息”；并且所有运算都是整数模运算，没有浮点误差。）

随机选取一个次数为 $k-1$ 的多项式 \(P(x) = a_{k-1}x^{k-1} + \cdots + a_1 x + s,\) 其中常数项就是秘密 $s = P(0)$，其余 $k-1$ 个系数 $a_1, \ldots, a_{k-1}$ 均匀随机选取。这 $k-1$ 个随机系数是”牺牲信息 (sacrificial information)”，它们的唯一作用是把秘密藏起来。

然后分发份额 (shares)：第 $i$ 位官员拿到 $P(i)$。

方案正确性证明

性质 1：任意 $k$ 名官员可以恢复 $s$。

$k$ 名官员手上共有 $k$ 个点 $(i_1, P(i_1)), \ldots, (i_k, P(i_k))$，横坐标两两不同。由插值定理 7.6（取 $d = k-1$，$d+1 = k$），存在唯一一个次数 $\le k-1$ 的多项式经过这 $k$ 个点。而 $P$ 就是这样一个多项式，所以它就是唯一解。官员们用拉格朗日插值显式地算出这个多项式，然后求 $P(0) = s$。

用”表示转换”的话说：$k$ 个份额恰好构成 $P$ 的一个取值表示，插值把取值表示转成系数表示，而系数表示里直接可以看到常数项 $s$。

性质 2：任意 $k-1$ 名（或更少）官员得不到关于 $s$ 的任何信息。

设有 $k-1$ 名官员，他们知道点 $(i_1, y_1), \ldots, (i_{k-1}, y_{k-1})$，想求 $P(0) = s$。

对秘密的任意一个候选值 $b \in \mathbb{F}q$（共 $q$ 种可能），考虑扩充点集 \((0, b), (i_1, y_1), \ldots, (i_{k-1}, y_{k-1}).\) 这共有 $1 + (k-1) = k$ 个点，且横坐标 $0, i_1, \ldots, i{k-1}$ 两两不同（因为各 $i_j \ge 1$ 而 $0$ 不在其中，$i_j$ 之间也不同）。由插值定理 7.6，存在唯一一个次数 $\le k-1$ 的多项式经过这 $k$ 个点。

也就是说：每一个可能的秘密值 $b$ 都恰好对应一个与官员们已知份额完全相容的次数 $k-1$ 多项式。官员们看到的 $k-1$ 个份额，对 $q$ 个可能的 $s$ 值完全对称——没有任何一个 $b$ 比其他更”合理”。所以他们的信息与零信息不可区分：对 $s$ 的后验分布就是均匀分布。

用”表示”的话说：官员们的信息与 $q$ 个不同的取值表示相容，每个对应一个可能的秘密值。

一个完整的秘密共享算例（$\mathbb{F}_7$）

设秘密 $s = 1$，$n = 5$ 名官员，门限 $k = 3$。取质数 $q = 7$（满足 $7 > s = 1$ 且 $7 > n = 5$）。

随机选取次数 $k - 1 = 2$ 的多项式，其常数项必须是 $s = 1$。假定随机系数选为 $a_2 = 3$、$a_1 = 5$：

分发份额：

（验算：$9 - 7 = 2$；$23 - 21 = 2$；$43 - 42 = 1$；$69 - 63 = 6$；$101 - 98 = 3$ ✔）

恢复：官员 3、4、5 集合。 他们拿到 $(3, 1), (4, 6), (5, 3)$。

构造拉格朗日基（$\mathbb{F}_7$ 中 $2^{-1} = 4$，$(-1)^{-1} = 6$）：

组合：

三人在 $x = 0$ 处求 $P(0)$（不必展开全部系数）。注意每个基函数在 $x=0$ 的值：

• $\Delta_3(0) = 4 \cdot (0-4)(0-5) = 4 \cdot (-4)(-5) = 4 \cdot 20 = 80 \equiv 80 - 77 = 3 \pmod 7$
• $\Delta_4(0) = 6 \cdot (0-3)(0-5) = 6 \cdot (-3)(-5) = 6 \cdot 15 = 90 \equiv 90 - 84 = 6 \pmod 7$
• $\Delta_5(0) = 4 \cdot (0-3)(0-4) = 4 \cdot (-3)(-4) = 4 \cdot 12 = 48 \equiv 48 - 42 = 6 \pmod 7$

恢复出 $s = 1$ ✔。也可以完整展开验证：三人恢复的 $P$ 在 $\mathbb{F}_7$ 上的取值表是 $(1,2,2,1,6,3,6)$，与真实的 $3x^2+5x+1$ 逐点相同 ✔。

“少于 $k$ 人一无所知”的具体演示。 官员 1 和 5 集合，拿到 $(1, 2)$ 与 $(5, 3)$。他们知道 $P(x) = a_2 x^2 + a_1 x + s$，于是知道两个方程：

两个方程、三个未知数——解不出唯一解。更精确地说，对秘密的每个候选 $s = 0,1,\ldots,6$，都能补出一个唯一的相容多项式：

七个 $s$ 值对应七个互不相同的、与已知份额完全相容的候选多项式。两人无法从份额中区分哪个 $s$ 是真的，所以”两个官员合起来”与”一个官员单独”对 $s$ 的信息量完全一样——这正是门限方案要求的强安全性。

与后续内容的联系

• 插值定理是纠错码 (error-correcting codes) 的基石。下一讲的 Reed-Solomon 码就是把消息编码成一个多项式在各点的取值，用 $n$ 个符号传 $k$ 个消息符号；即使信道把部分符号搞错（不只是丢失，而是错误成别的值），只要错误数控制在阈值内，接收方仍能用 Berlekamp-Welch 算法恢复原消息——其核心正是”找两个多项式，用插值和根定理夹逼出真相”。
• Schwartz-Zippel 引理（引理 7.8）用在多项式恒等式检验和随机化算法中，也是概率方法（讲次 23 的集中不等式）的一个优雅应用。

与其他讲次的关联

• 讲次 4（Modular Arithmetic，模运算）：有限域 $\mathbb{F}_p$ 的加、减、乘、除全部是讲次 4 的模运算。$\mathbb{F}_p$ 之所以能叫”域”，正是因为讲次 4/5 证明了 $\mathbb{Z}_p$ 中每个非零元都有乘法逆元。拉格朗日插值在 $\mathbb{F}_p$ 上的实现就是”除以 $x_i - x_j$”= “乘以 $(x_i - x_j)^{-1} \bmod p$”，本讲算例 B 中 $2^{-1} = 4$、$(-1)^{-1} = 6$ 就是这个道理。
• 讲次 5（Euclid, FLT, CRT）：
  • 费马小定理 (FLT) 直接给出 $x^p \equiv x \pmod p$，这是”$\mathbb{F}_p$ 上多项式函数不唯一（$x^p$ 与 $x$ 相同）”以及”$x^p - x$ 有 $p$ 个根”的唯一依据，也是命题 7.7 中”次数 $\ge p$ 的多项式可降次”的机制。
  • 中国剩余定理 (CRT) 与拉格朗日插值在结构上是同一件事：CRT 的基向量 $b_i$（在方向 $n_i$ 上取 1、其他方向取 0）与拉格朗日基 $\Delta_i$（在 $x_i$ 处取 1、其他点取 0）是一模一样的”指示函数”思想，解都是 $\sum a_i b_i$ 与 $\sum y_i \Delta_i$ 形式的线性组合。官方 Note 也明确指出 Lagrange 插值”should remind you of the Chinese Remainder Theorem”。
  • 扩展欧几里得算法是求 $(x_i - x_j)^{-1} \bmod p$ 的工具，没有它就写不出 $\Delta_i$。
• 讲次 3（Induction，归纳法）：定理 7.3（有限根定理）的证明是对次数 $d$ 的弱归纳；Claim A 的证明也是归纳。归纳假设的用法是”剥掉一个线性因子后，把次数小 1 的问题交回去”。
• 讲次 2（Proof Techniques II，反证/分情形）：插值定理的唯一性部分用反证法（假设存在第二个多项式，导出矛盾）；有限根定理在推导”根数 $\le d$”时用了分情形（有根 / 无根）。
• 讲次 6（RSA，RSA 加密）：两个讲次共享”单向结构“的设计哲学——RSA 用”正向做幂容易、逆向求离散对数/分解困难”，本讲用”给定系数求值容易（$O(d)$ 次乘加）、给定取值求系数需要 $d+1$ 个点（少了就不唯一）”。本讲末尾提到的随机填充与 Schwartz-Zippel 的”随机取点检验”都用同一招：引入随机性把确定性的结构漏洞堵住。
• 讲次 8（Secret Sharing & ECC，秘密共享与纠错码）：本讲的插值定理、根定理、Schwartz-Zippel 引理在下一讲被直接使用——Shamir 秘密共享 = 插值定理；Reed-Solomon 码 = 取值表示 + 插值；Berlekamp-Welch 解码 = 根定理 + 线性代数。可以说本讲是下一讲的全部数学预备。
• 讲次 14（Counting，计数）：本讲”$\mathbb{F}_p$ 上过 $d-k$ 个点的次数 $\le d$ 多项式有 $p^{k+1}$ 个”这张计数表，用的是逐层自由选择这一基本计数原理；”任意 $k$ 名官员可恢复、$k-1$ 名不可”的论证也用到了”每个秘密候选值对应唯一多项式”的双射计数。

关键要点

1. 有限根定理：在域上，次数为 $d$ 的非零多项式至多有 $d$ 个根。两个条件都不可省——”非零”（零多项式处处为零）与”域”（$\mathbb{Z}_8$ 上 $x^3$ 有 4 个根）。上界紧：$\mathbb{F}_7$ 上 $x(x-1)(x-2)$ 恰有 3 个根，$x^7 - x$ 恰有 7 个根。
2. 因式定理：$(x-r) \mid P(x) \iff P(r) = 0$。这是从”求值”跳到”代数结构”的桥，也是根定理归纳证明的发动机。
3. 插值定理：$d+1$ 个横坐标互不相同的点存在且唯一确定一个次数 $\le d$ 的多项式。存在性由拉格朗日基 $\Delta_i(x) = \prod_{j\ne i}\frac{x-x_j}{x_i-x_j}$ 构造性给出，$P = \sum_i y_i \Delta_i$；唯一性由”差多项式有 $d+1$ 个根但次数 $\le d$，矛盾”给出。
4. 域 vs 非域的分界线是”没有零因子”。所有证明只用到”加、减、乘、除（非零）”四则运算封闭这一条。$\mathbb{Z}_p$（$p$ 质数）、$\mathbb{Q}$、$\mathbb{R}$、$\mathbb{C}$ 都可以；$\mathbb{Z}_8$、$\mathbb{N}$、$\mathbb{Z}$ 都不行（$\mathbb{Z}$ 上还有别的失效原因：$\frac{1}{2}$ 不存在，$y = x/2$ 类型的插值多项式无法表示）。
5. 函数 ≠ 多项式（在有限域上）。$\mathbb{F}_p$ 上 $x^p$ 与 $x$ 作为函数完全相同、作为多项式不同。加上”次数 $\le p-1$”这个限制后，函数与多项式一一对应（命题 7.7）——这是”用 $d+1$ 个点指定 $d$ 次多项式”能成立而不引起歧义的根本原因。
6. Schwartz-Zippel：若 $P \ne Q$ 且 $\deg P, \deg Q \le d$，则随机 $r$ 满足 $P(r) = Q(r)$ 的概率 $\le d/p$。这是”随机点上求值检验多项式相等”的可靠性保证。

常见误区与注意事项

1. 忘记”非零”条件。零多项式 $P(x) \equiv 0$ 有无穷多个根（在 $\mathbb{R}$ 上）、$p$ 个根（在 $\mathbb{F}_p$ 上），完全不受”至多 $d$ 个根”的约束。在写根定理和插值唯一性证明时必须明确”$P \ne Q$ 所以 $P - Q$ 是非零多项式”。若两个多项式确实相等，差是零多项式，这个论证立刻失效——而这恰恰就是唯一性想要证明的结论，所以论证的逻辑顺序不能反。

2. 把”至多 $d$ 个根”读成”恰有 $d$ 个根”。定理只是上界。在 $\mathbb{R}$ 上 $x^2+1$ 是 0 个根；在 $\mathbb{F}_p$ 上很多多项式根数远少于次数。另外，$x^2 - 4$ 在 $\mathbb{R}$ 上有 2 个根（$2$ 与 $-2$），但在 $\mathbb{F}_5$ 上 $x^2 - 4 = x^2 + 1$ 的根是 $2$ 与 $3$（$3^2 = 9 \equiv 4$，$4 - 4 = 0$ ✔；等等，$3^2 - 4 = 5 \equiv 0$ ✔）——同一个系数模式在不同域上根完全不同，数根时必须指明在哪个域中数。

3. 误以为插值定理对任意 $m$ 的 $\mathbb{Z}_m$ 都成立。定理要求系数取自域。在 $\mathbb{Z}_8$ 上，$x^3$ 有 4 个根，于是”过 4 个点（含 $0,2,4,6$）的唯一 3 次多项式”这一断言直接崩掉（$x^3$ 与零多项式在 $0,2,4,6$ 上取值全同，但它们是不同的多项式）。$m$ 必须是质数。

4. 把 $\mathbb{Z}_m$ 与 $\mathbb{F}_m$ 混为一谈。官方 Note 特别强调：虽然存在含 8 个元素的域（记作 $\mathbb{F}_8$ 或 $GF(8)$），但它不是 $\mathbb{Z}_8$。$\mathbb{Z}_8$ 无法嵌入任何更大的域中让根定理”复活”。看到 $\mathbb{F}_m$ 时，先确认 $m$ 是质数。

5. 混淆”系数表示相等”与”函数相等”。$x^7$ 与 $x$ 在 $\mathbb{F}_7$ 上处处取值相同，但它们是两个不同的多项式（次数不同），在系数意义下绝不相等。做多项式运算（相加、相乘、比较次数、判断整除）时必须用系数观点；只有在讨论”取值表”时才用函数观点。判断两者是否可能相等时，先看次数是否都 $\le p-1$。

6. 插值从不回代验算。这是最容易丢分的地方。任何插值结果都应当把 $x_i$ 逐个代回去检查是否等于 $y_i$。典型例子：$(0,1),(1,2),(2,5)$ 的正确答案是 $P(x) = x^2 + 1$，但很容易算成 $1 + \frac{1}{2}x + \frac{3}{2}x^2$（代入 $x = 1$ 得 $3 \ne 2$，立刻暴露错误）。代回验算是插值题唯一可靠的检查方式。

7. 在模运算中把”除法”当成普通除法。$\mathbb{F}_p$ 上 $\frac{1}{2}$ 不是 $0.5$，而是 $2^{-1} \bmod p$（$\mathbb{F}_7$ 上是 4，$\mathbb{F}_5$ 上是 3）。写拉格朗日基时把分母 $\prod (x_i - x_j)$ 直接搬到实数上算，结果会完全错。正确做法：先算出分母的模 $p$ 值，再乘它的模 $p$ 逆元。

8. 忽略”$x_i$ 必须两两不同”。这是插值定理的硬性前提。取 $(0, 1)$ 与 $(0, 2)$ 两点，要求同一个多项式在 $x = 0$ 处同时取 1 和 2——连存在性都没有（在 $\mathbb{F}_7$ 上逐一遍历 343 个次数 $\le 2$ 的多项式，满足这两点的个数是 0）。前提不满足时，唯一性自然更谈不上。

思考题（带答案）

Q1. （纯计算）在 $\mathbb{F}_7$ 上求过 $(0, 3), (1, 0), (2, 3)$ 的次数 $\le 2$ 的多项式，用拉格朗日插值逐步写出三个基多项式与最终系数，并代入三个点验算。

Q2. （概念 / 证明）在 $\mathbb{Z}_8$ 上，$P(x) = x^3$ 有 4 个根，违反根定理。请具体指出定理 7.3 的证明在哪一步、因为哪一条性质失效而崩溃；然后说明为什么”$m$ 是质数”这个条件在本讲的框架里是不可替代的。

Q3. （概念 / 计数）在 $\mathbb{F}_7$ 上，次数 $\le 2$ 的多项式共 $7^3 = 343$ 个。（a）过给定的 1 个点、2 个点、3 个（横坐标互不相同的）点的次数 $\le 2$ 多项式各有多少个？（b）解释这张计数表如何”改写”成插值定理的一个证明；（c）如果放宽到次数 $\le 3$，过 3 个点又有多少个？并说明为什么这个数字与 $(a)$ 中过 3 个点的答案不同。