知识焦点
先建立概念地图
- polynomial roots
- finite field
- GF(p)
- Lagrange interpolation
- secret sharing
- Shamir secret sharing
- polynomial degree
- FLT
CS70 · 讨论课 04b
本练习涵盖四个主题：(1) 实系数多项式与有限域 GF(p) 上多项式的根的个数；(2) 有限域上的拉格朗日插值；(3) 基于多项式插值的联合国秘密共享方案设计；(4) 恶意参与者通过篡改共享值破坏秘密重构的攻击分析。
知识焦点
建议顺序
先完整作答，再按需展开提示；最后才展开官方参考解答并逐步核对证明与计算。
本地来源
题面与解答均由本地一手资料整理：discussion/dis04b.pdf、solutions/discussion/dis04b-sol.pdf
本地一手资料完整提取 · 讨论课
本节按本地一手资料完整整理，共 4 道大题。本地官方解答已完整收录并默认折叠；建议先独立完成，再逐题核对推导。
discussion/dis04b.pdf、solutions/discussion/dis04b-sol.pdfNote 8
设 \(f\) 与 \(g\) 是非零实系数多项式。
(a) 下列多项式至少有多少个根？至多有多少个根？（答案可能依赖于 \(f\) 与 \(g\) 的次数。）
(i) \(f + g\)
(ii) \(f \cdot g\)
(iii) \(f / g\)，假设 \(f / g\) 是一个多项式
(b) 现在设 \(f\) 与 \(g\) 是 \(\mathrm{GF}(p)\) 上的多项式。
(i) 我们称多项式 \(f = 0\) 当且仅当 \(\forall x,\ f(x) = 0\)。若 \(f \cdot g = 0\)，是否一定有 \(f = 0\) 或 \(g = 0\)？
(ii) 有多少个次数恰好为 \(d < p\) 的多项式 \(f\) 满足 \(f(0) = a\)，其中 \(a \in \{0, 1, \ldots, p - 1\}\) 是某个固定的值？
(c) 在 \(\mathrm{GF}(5)\) 上找一个多项式 \(f\) 满足 \(f(0) = 1\)、\(f(2) = 2\)、\(f(4) = 0\)。这样的次数至多为 4 的多项式有多少个？
（a）考虑结果多项式的次数与实系数多项式根的基本性质；对 \(f+g\) 留意最高次项相消及 \(f = -g\) 的特殊情形。 （b）在有限域上，多项式的零点可在不同点分别分布，\(f \cdot g = 0\) 只要求在每一点至少有一个因子为零；计数时考虑系数空间的约束条件。 （c）先用拉格朗日插值或待定系数法构造一个满足条件的多项式，再分析剩余的自由度。
(a)
(i) \(f + g\) 可能完全没有根（例如 \(f(x) = 2x^2 - 1\) 且 \(g(x) = -x^2 + 2\)），因此最少根的个数为 0。然而，若 \(f + g\) 的最高次数为奇数，则它至少穿过 x 轴一次，即奇次数多项式最少有 1 个根。
另一方面，\(f + g\) 是一个次数至多为 \(m = \max(\deg f, \deg g)\) 的多项式，因此它最多有 \(m\) 个根。唯一的例外是若 \(f = -g\)，此时 \(f + g = 0\)，多项式有无穷多个根！
(ii) 乘积为零当且仅当其中一个因子为零。因此若 \(f(x) \cdot g(x) = 0\) 对某个 \(x\) 成立，则 \(x\) 是 \(f\) 的根或 \(g\) 的根，这给出最多 \(\deg f + \deg g\) 个可能。
同样，若 \(f\) 与 \(g\) 都没有根，则乘积也可能没有根（例如 \(f(x) = g(x) = x^2 + 1\)）。
(iii) 若 \(f/g\) 是一个多项式，则它的次数必为 \(d = \deg f - \deg g\)，因此最多有 \(d\) 个根。
同样，它可能没有根，例如若 \(f(x) = g(x)(x^2 + 1)\)，则 \(f/g = x^2 + 1\) 没有根。
(b)
(i) 这里有几个反例：
例 1：\(x^{p-1} - 1\) 与 \(x\) 在 \(\mathrm{GF}(p)\) 上都是非零多项式（对任意 \(p\)）。\(x\) 在 0 处有根，而由费马小定理（FLT），\(x^{p-1} - 1\) 在 \(\mathrm{GF}(p)\) 的所有非零点处有根。因此它们的乘积 \(x^p - x\) 在 \(\mathrm{GF}(p)\) 的所有点处都为零。
例 2：要满足 \(f \cdot g = 0\)，只需 \((\forall x \in S,\ f(x) = 0 \lor g(x) = 0)\)，其中 \(S = \{0, \ldots, p-1\}\)。可以看出这不等价于 \((\forall x \in S,\ f(x) = 0) \lor (\forall x \in S,\ g(x) = 0)\)。
为构造一个具体例子，设 \(p = 2\)，令 \(f(0) = 1, f(1) = 0\)（例如 \(f(x) = 1 - x\)），且 \(g(0) = 0, g(1) = 1\)（例如 \(g(x) = x\)）。则 \(f \cdot g = 0\) 但 \(f\) 与 \(g\) 都不是零多项式。
(ii) 一般来说，\(f(x) = \sum_{k=0}^{d} c_k x^k\) 的 \(d+1\) 个系数中的每一个都可以取 \(p\) 个值中的任意一个。然而，条件 \(f(0) = a\) 与 \(\deg f = d\) 对常数项系数 \(f(0) = c_0 = a\) 与最高次项系数 \(c_d \neq 0\) 施加了约束。因此剩下 \((p-1) \cdot p^{d-1}\) 种可能。
(c) 一个次数 \(\leq 4\) 的多项式由 5 个点 \((x_i, y_i)\) 确定。我们已指定 3 个点，剩余 2 个自由点，每个可取 5 个值，共 \(5^2 = 25\) 种可能。为找到一个具体的多项式，使用拉格朗日插值：
\[\Delta_0(x) = 2(x-2)(x-4), \quad \Delta_2(x) = x(x-4), \quad \Delta_4(x) = 2x(x-2),\]
因此 \(f(x) = \Delta_0(x) + 2\Delta_2(x) = 4x^2 + 1\)。
解答来源：solutions/discussion/dis04b-sol.pdf · 1 · confidence: high
题面来源：discussion/dis04b.pdf · 1 · confidence: high
Note 8
在模 5 算术下，使用拉格朗日插值法求一个次数至多为 3 的唯一多项式 \(p(x)\)，使其通过点 \((-1, 3)\)、\((0, 1)\)、\((1, 2)\) 和 \((2, 0)\)。
(a) 求 \(p_{-1}(x)\)，其中 \(p_{-1}(0) \equiv p_{-1}(1) \equiv p_{-1}(2) \equiv 0 \pmod{5}\) 且 \(p_{-1}(-1) \equiv 1 \pmod{5}\)。
(b) 求 \(p_0(x)\)，其中 \(p_0(-1) \equiv p_0(1) \equiv p_0(2) \equiv 0 \pmod{5}\) 且 \(p_0(0) \equiv 1 \pmod{5}\)。
(c) 求 \(p_1(x)\)，其中 \(p_1(-1) \equiv p_1(0) \equiv p_1(2) \equiv 0 \pmod{5}\) 且 \(p_1(1) \equiv 1 \pmod{5}\)。
(d) 求 \(p_2(x)\)，其中 \(p_2(-1) \equiv p_2(0) \equiv p_2(1) \equiv 0 \pmod{5}\) 且 \(p_2(2) \equiv 1 \pmod{5}\)。
(e) 用 \(p_{-1}(x)\)、\(p_0(x)\)、\(p_1(x)\) 和 \(p_2(x)\) 的线性组合构造 \(p(x)\)。
拉格朗日基多项式 \(p_i(x)\) 在节点 \(x_i\) 处取值 1，在其他节点处取值 0。利用这一性质，先写出基多项式的表达式并计算归一化系数（即分母的模逆元），再做线性组合。
(a)
\[p_{-1}(x) \equiv x(x-1)(x-2) \cdot [(-1)(-1-1)(-1-2)]^{-1} \equiv x(x-1)(x-2) \cdot (-6)^{-1} \equiv 4x(x-1)(x-2) \pmod{5}.\]
（在 \(\mathrm{GF}(5)\) 中，\(-6 \equiv 4\)，且 \(4^{-1} \equiv 4\)（因为 \(4 \cdot 4 = 16 \equiv 1\)）。）
(b)
\[p_0(x) \equiv (x+1)(x-1)(x-2) \cdot [(1)(-1)(-2)]^{-1} \equiv 3(x+1)(x-1)(x-2) \pmod{5}.\]
（在 \(\mathrm{GF}(5)\) 中，\((1)(-1)(-2) = 2\)，且 \(2^{-1} \equiv 3\)（因为 \(2 \cdot 3 = 6 \equiv 1\)）。）
(c)
\[p_1(x) \equiv (x+1)(x)(x-2) \cdot [(2)(1)(-1)]^{-1} \equiv 2(x+1)(x)(x-2) \pmod{5}.\]
（在 \(\mathrm{GF}(5)\) 中，\((2)(1)(-1) = -2 \equiv 3\)，且 \(3^{-1} \equiv 2\)（因为 \(3 \cdot 2 = 6 \equiv 1\)）。）
(d)
\[p_2(x) \equiv (x+1)(x)(x-1) \cdot (6)^{-1} \equiv (x+1)(x)(x-1) \pmod{5}.\]
（在 \(\mathrm{GF}(5)\) 中，\(6 \equiv 1\)，且 \(1^{-1} = 1\)。）
(e) 我们不需要 \(p_2(x)\)（因为 \(x=2\) 处的 y 值为 0）。
\[p(x) \equiv 3 \cdot p_{-1}(x) + 1 \cdot p_0(x) + 2 \cdot p_1(x) + 0 \cdot p_2(x) \equiv 4x^3 + 4x^2 + 3x + 1 \pmod{5}.\]
解答来源：solutions/discussion/dis04b-sol.pdf · 2 · confidence: high
题面来源：discussion/dis04b.pdf · 2 · confidence: high
Note 8
联合国的一个保险箱可以用一个秘密组合 \(s \in \mathbb{Z}\) 打开。只有在以下两种情况下才应打开该保险箱：(i) 所有 193 个成员国必须同意，或 (ii) 至少 55 个国家加上联合国秘书长必须同意。
(a) 提出一个方案，为秘书长和所有 193 个成员国分配私有信息，使得秘密组合 \(s\) 仅能在上述两种情况之一下被恢复。
(b) 联合国大会决定增加一层安全性：193 个成员国各有 12 名代表，所有这些代表必须同意才能使该国帮助打开保险箱。提出一个方案以增加这一新特性。该方案应为秘书长和每个国家的每名代表分配私有信息。
Shamir 秘密共享中，\(k\) 个点可以确定一个次数不超过 \(k-1\) 的多项式。考虑如何让秘书长持有的点数恰好补足 55 个国家到重构阈值 193；对 (b) 可在每个国家内部再做一层门限为 12 的秘密共享。
(a) 构造一个次数为 192 的多项式，给每个国家一个点。给秘书长 \(193 - 55 = 138\) 个点，这样若她与 55 个国家合作，共有 193 个点，可以重构多项式。没有秘书长的情况下，若所有 193 个国家聚集，仍可恢复多项式。（我们在 \(\mathrm{GF}(p)\) 中进行所有运算，其中 \(p \geq d + 1\)。）
或者，我们可以为条件 (i) 和条件 (ii) 各设一个方案。第一个条件是笔记中讨论过的秘密共享设置，一个次数为 192 的多项式即可满足，每个国家收到一个点，在零处的取值返回组合 \(s\)。对于第二个条件，构造一个次数为 1 的多项式 \(f\) 满足 \(f(0) = s\)，并将 \(f(1)\) 给秘书长。再构造第二个次数为 54 的多项式 \(g\)，满足 \(g(0) = f(2)\)，并将 \(g\) 的一个点给每个国家。这样任意 55 个国家可以恢复 \(g(0) = f(2)\)，然后与秘书长协商从 \(f(1)\) 和 \(f(2)\) 恢复 \(s = f(0)\)。
(b) 我们在 (a) 部分的方案上再叠加一层秘密共享。若 \(t_i\) 是给第 \(i\) 个国家的密钥，构造一个次数为 11 的多项式 \(f_i\) 满足 \(f_i(0) = t_i\)，并将 \(f_i\) 的一个点给 12 名代表中的每一位。对每个国家都这样做（每次使用不同的 \(f_i\)）。
解答来源：solutions/discussion/dis04b-sol.pdf · 3 · confidence: high
题面来源：discussion/dis04b.pdf · 2 · confidence: high
Note 8
发射火箭需要一个秘密数字 \(s\)，Alice 将一个次数为 \(n\) 的多项式 \(p\) 的值 \((1, p(1))\)、\((2, p(2))\)、⋯⋯、\((n+1, p(n+1))\) 分发给一组 GME 持有者 \(\mathrm{Bob}_1, \ldots, \mathrm{Bob}_{n+1}\)。像往常一样，她选择 \(p\) 使得 \(p(0) = s\)。\(\mathrm{Bob}_1\) 到 \(\mathrm{Bob}_{n+1}\) 现在聚在一起共同发现秘密。然而，\(\mathrm{Bob}_1\) 秘密地是 Melvin Capital 的合伙人，他已经知道 \(s\)，并想破坏 \(\mathrm{Bob}_2, \ldots, \mathrm{Bob}_{n+1}\)，让他们相信秘密实际上是某个固定的 \(s' \neq s\)。他如何做到这一点？换句话说，他应该报告什么值（用问题中已知的变量表示，如 \(s'\)、\(s\) 或 \(y_1\)）才能使其他人相信秘密是 \(s'\)？
\(\mathrm{Bob}_1\) 需要让拉格朗日插值在 \(x=0\) 处的结果从 \(s\) 变为 \(s'\)。利用插值公式在 \(x=0\) 处的表达式，分析改变 \(y_1\) 对最终结果的影响，并解出应报告的值 \(y_1'\)。
我们知道，为了发现 \(s\)，Bob 们会计算
\[s = y_1 \Delta_1(0) + \sum_{k=2}^{n+1} y_k \Delta_k(0), \tag{1}\]
其中 \(y_i = p(i)\)。\(\mathrm{Bob}_1\) 现在想将他的值 \(y_1\) 改为某个 \(y_1'\)，使得
\[s' = y_1' \Delta_1(0) + \sum_{k=2}^{n+1} y_k \Delta_k(0). \tag{2}\]
将式 (1) 从式 (2) 中减去并解出 \(y_1'\)，我们看到
\[y_1' = (\Delta_1(0))^{-1} (s' - s) + y_1,\]
其中 \((\Delta_1(0))^{-1}\) 存在，因为 \(\deg \Delta_1(x) = n\)，其 \(n\) 个根在 \(2, \ldots, n+1\)（因此 \(\Delta_1(0) \neq 0\)）。
解答来源：solutions/discussion/dis04b-sol.pdf · 4 · confidence: high
题面来源：discussion/dis04b.pdf · 3 · confidence: high
discussion/dis04b.pdfsolutions/discussion/dis04b-sol.pdf