GF(p) 多项式、单点插值、CRT 与 Lagrange、秘密共享、纠错码、Alice 与 Bob

(a) 费马小定理指出，对于任意非零整数 a 和任意素数 p，有 aᵖ⁻¹ ≡ 1 (mod p)。我们可以在两边同乘以 a，因此该定理等价于说 aᵖ ≡ a (mod p)；注意即使当 a = 0 时也成立，因为此时我们有 0ᵖ ≡ 0 (mod p)。

题目要求找一个多项式 f̃(x)，不同于 f(x)，但满足对任意整数 a 都有 f̃(a) ≡ a⁵ (mod 5)。直接应用定理，f̃(x) = x 即可。

对于 g(x) = 4x⁷⁰ + 9x¹¹ + 70 模 11，由于 x¹¹ ≡ x (mod 11)，我们可以设 ḡ(x) = 4x¹⁰ + 9x + 4。

(b) 证明一（使用费马小定理）：作为热身，设 d ≥ p；我们来找一个等价于 xᵈ 的多项式。对于任意整数 a，我们知道

aᵈ = aᵈ⁻ᵖ · aᵖ ≡ aᵈ⁻ᵖ · a ≡ aᵈ⁻ᵖ⁺¹ (mod p)

换句话说，xᵈ 等价于多项式 xᵈ⁻⁽ᵖ⁻¹⁾。如果 d − (p−1) ≥ p，我们可以用同样的方法证明 xᵈ 等价于 xᵈ⁻²⁽ᵖ⁻¹⁾。由于每次减去 p−1，序列 d, d−(p−1), d−2(p−1), … 最终必然小于 p。现在，如果 f(x) 是任意次数 ≥ p 的多项式，我们可以对每个出现的 xᵏ（其中 k ≥ p）应用同样的技巧。

证明二（使用拉格朗日插值）：设 f(x) 的次数 ≥ p。由拉格朗日插值，存在唯一的次数至多为 p−1 的多项式 f̃(x) 经过点 (0, f(0)), (1, f(1)), (2, f(2)), …, (p−1, f(p−1))，我们这样设计它恰好使其等价于 f(x)。

(a) 可以。由于首项系数为 1，我们只需找到剩下的 \(k\) 个系数 \(c_0, c_1, \ldots, c_{k-1}\) 即可确定 \(f(x)\)。这可以通过任意 \(k\) 个不同的点来完成。

例如，假设我们知道点 \((0, f(0)), (1, f(1)), \ldots, (k-1, f(k-1))\)。然后我们可以写出次数为 \(k-1\) 的多项式 \[g(x) = c_{k-1}x^{k-1} + \cdots + c_2x^2 + c_1x + c_0 = f(x) - x^k\] 该多项式可以通过对点 \((0, f(0)), (1, f(1) - 1), (2, f(2) - 2^k), \ldots, (k-1, f(k-1) - (k-1)^k)\) 进行拉格朗日插值来确定，从而唯一地得到我们想要的系数 \(c_0, c_1, \ldots, c_{k-1}\)。

(b) 可以。我们可以将每个非负的两位整数 \(c_i\) 表示为 \(c_i = 10d_{2i+1} + d_{2i}\)，其中数字 \(d_i \in [0,9]\)。

取 \(x^* = 100\)， \[f(100) = 100^k + c_{k-1}100^{k-1} + \cdots + c_2 \cdot 100^2 + c_1 \cdot 100 + c_0\] \[= 10^{2k} + (10d_{2k-1} + d_{2k-2})10^{2k-2} + \cdots + (10d_5 + d_4)10^4 + (10d_3 + d_2)10^2 + (10d_1 + d_0)\] \[= 10^{2k} + 10^{2k-1}d_{2k-1} + 10^{2k-2}d_{2k-2} + \cdots + 10^5d_5 + 10^4d_4 + 10^3d_3 + 10^2d_2 + 10d_1 + d_0\]

因此，\(f(100)\) 的最右边 \(2k-1\) 个数字，从右到左依次是 \(d_0, d_1, \ldots, d_{2k-1}\)；然后我们可以确定想要的系数 \(c_i = 10d_{2i+1} + d_{2i}\)。

(a) 由于 \(\gcd(n_1, n_2) = 1\)，存在整数 \(k_1, k_2\) 使得 \(1 = k_1n_1 + k_2n_2\)。令 \(x_1 = k_2n_2 = 1 - k_1n_1\) 且 \(x_2 = k_1n_1 = 1 - k_2n_2\)，我们得到两个想要的解。

(b) 利用我们在 (a) 中找到的 \(x_1\) 和 \(x_2\)，我们证明 \(a_1x_1 + a_2x_2\)（模 \(n_1n_2\)）是想要的同余式的解： \[a_1x_1 + a_2x_2 \equiv a_1 \cdot 1 + a_2 \cdot 0 \equiv a_1 \pmod{n_1}\] \[a_1x_1 + a_2x_2 \equiv a_1 \cdot 0 + a_2 \cdot 1 \equiv a_2 \pmod{n_2}\] 该解也是唯一的。假设有两个不同的解 \(x = c\) 和 \(x = c'\)，它们都满足 \(x \equiv a_1 \pmod{n_1}\) 和 \(x \equiv a_2 \pmod{n_2}\)。这将给出 \(c \equiv c' \pmod{n_1}\) 和 \(c \equiv c' \pmod{n_2}\)，说明 \((c - c')\) 能被 \(n_1\) 和 \(n_2\) 整除。由于 \(n_1\) 和 \(n_2\) 互素，\(\gcd(n_1, n_2) = 1\)，所以 \((c - c')\) 能被 \(n_1n_2\) 整除。用模形式写出即得 \(c \equiv c' \pmod{n_1n_2}\)。因此，所有解在模 \(n_1n_2\) 下是唯一的。

(c) 我们对 \(k\) 使用归纳法。(b) 处理了基础情况 \(k=2\)。对于归纳假设，假设对于 \(k \leq l\)，方程组 (1)-(k) 有唯一解 \(a\)（模 \(n_1\cdots n_k\)）。现在考虑 \(k = l+1\)，我们将方程 \(x \equiv a_{l+1} \pmod{n_{l+1}}\) 加入方程组，得到 \[x \equiv a \pmod{n_1\cdots n_l}\] \[x \equiv a_{l+1} \pmod{n_{l+1}}\] 由于 \(n_i\) 两两互素，\(n_1n_2\cdots n_l\) 和 \(n_{l+1}\) 互素。(b) 告诉我们存在唯一解 \(a'\)（模 \(n_1\cdots n_l n_{l+1}\)）。我们得出结论：\(a'\) 是 (1)-(l+1) 的唯一解（模 \(n_1n_2\cdots n_l n_{l+1}\)）。

(d) 我们只需验证当 \(x_i \neq x_j\) 时，\(q_i(x) = (x - x_i)\) 和 \(q_j(x) = (x - x_j)\) 互素，即它们没有次数为 1 的公因式。如果 \(d_i(x) = a_ix + b_i\) 是 \(q_i(x)\) 的因式，则 \(q_i(x) = q'(x)(a_ix + b_i)\) 对某个多项式 \(q'(x)\) 成立。但由于 \(q_i(x)\) 次数为 1，\(q'(x)\) 必须次数为 0 从而为常数，所以 \(d_i(x)\) 必须是 \(q_i(x)\) 的常数倍。类似地，\(q_j(x)\) 的任何次数为 1 的因式 \(d_j\) 必须是 \(q_j(x)\) 的常数倍，且如果 \(x_i \neq x_j\)，则这些常数倍没有重叠，所以 \(q_i(x)\) 和 \(q_j(x)\) 互素。

由 (d) 的结果，同余式 (1')-(k') 表明我们正在寻找一个多项式 \(p(x)\) 使得 \(p(x_i) = y_i\)。然后 CRT 建立了 \(p(x)\) 的存在性，且它在模一个次数为 \(k\) 的多项式下唯一。也就是说，如果 \(p(x)\) 的次数至多为 \(k-1\)，则 \(p(x)\) 唯一。拉格朗日插值找到了 \(p(x)\)。

（以下为官方解答的翻译，保留两种解法。）

解法一（分层秘密共享）

该秘密由两部分组成：一个全体一致秘密 \(U\) 和一个多种族秘密 \(M\)。\(U\) 确保至少有一个种族的所有成员同意，而 \(M\) 确保至少有两个不同种族的成员同意。

整体思路是：魔戒的秘密只有在全体一致条件和多种族条件均被满足时才能获得。我们将原始秘密编码在一个一次多项式 \(R(x)\) 中，该多项式由两个值 \(U\) 和 \(M\) 唯一确定；\(U\) 和 \(M\) 各自又分别被编码为独立的多项式秘密，分别在满足全体一致条件和多种族条件时才能被恢复。一旦 \(U\) 和 \(M\) 都被恢复，就可以组合它们来揭示原始秘密，因为它们分别是该一次多项式 \(R(x)\) 上的两个点，而 \(R(x)\) 在 \(y\) 轴上的截距包含魔戒的秘密。

下面分别详述 \(U\) 和 \(M\)。

全体一致秘密 \(U\)：为每个种族分别创建一个独立的秘密，要求该种族的所有成员齐心协力才能揭示该秘密。例如，每个人类持有一个四次多项式（degree-4 polynomial）上的不同点，每个霍比特人持有一个一次多项式上的不同点。当一个种族的所有成员聚集在一起时，他们将揭示 \(U\)（例如编码为这些多项式中每一个的 \(y\) 轴截距）。注意，精灵和矮人由于各自是所属种族的唯一成员，因此他们已经知道 \(U\)。

多种族秘密 \(M\)：创建一个一次多项式 \(P_m(x)\)，并将一个点发给每个种族的成员。例如，每个霍比特人得到 \(P_m(1)\)，精灵得到 \(P_m(2)\)，每个人类得到 \(P_m(3)\)，矮人得到 \(P_m(4)\)。这样，只要来自任意两个不同种族的成员达成一致，就可以揭示 \(M\)（例如编码为 \(P_m(x)\) 的 \(y\) 轴截距）。

一旦 \(U\) 和 \(M\) 各自已知，就可以组合它们来确定最终秘密。\(U\) 和 \(M\) 允许我们唯一地确定 \(R(x)\)，从而得到 \(R(0)\)，即魔戒的秘密。

该方案是分层秘密共享（hierarchical secret sharing）的一个示例。下面给出一个具体实例。

示例：假设秘密 \(s = 4\)，\(M = 3\)，\(U = 2\)。此后可以在 \(\mathrm{GF}(7)\) 中运算，因为 \(s < 7\) 且 \(n < 7\)（\(n\) 为持有秘密份额的人数）。

首先需要构造一个一次多项式 \(R(x)\)，使得 \(R(0) = s = 4\)，\(R(1) = M = 3\)，\(R(2) = U = 2\)。通过观察可得 \(R(x) = 6x + 4\) 满足这些性质（例如 \(R(1) = 6 \cdot 1 + 4 = 10 \equiv 3 \pmod{7}\)）。

接下来创建多种族秘密 \(M\)。选择一次多项式 \(P_m(x) = x + 3\)，并告知每个霍比特人 \(P_m(1) = 4\)，精灵 \(P_m(2) = 5\)，每个人类 \(P_m(3) = 6\)，矮人 \(P_m(4) = 7 \equiv 0\)。现在，来自任意两个不同种族的任意两名成员可以通过插值确定 \(P_m(x)\) 从而得到 \(P_m(0)\)。

在创建全体一致秘密 \(U\) 时，首先注意到矮人和精灵将直接被告知 \(U\)，因为他们是各自种族的唯一成员。另一方面，霍比特人各自持有一次多项式 \(P_{\text{hobbits}}(x)\) 上的一个点。假设 \(P_{\text{hobbits}}(x) = 2x + 2\)，则第一个霍比特人收到 \(P_{\text{hobbits}}(1) = 4\)，第二个霍比特人收到 \(P_{\text{hobbits}}(2) = 4 + 2 = 6\)。当他们用这些值进行插值时，将发现原始多项式，从而得到 \(P_{\text{hobbits}}(0) = U = 2\)。人类将拥有一个类似的秘密，但使用一个四次多项式。

现在假设两名霍比特人和一名人类聚集在一起。两名霍比特人协作，如上所述确定 \(U\)。他们三人还知道 \(P_m(3) = 6\) 和 \(P_m(1) = 4\)，从中可以求出 \(P_m(x)\) 从而得到 \(P_m(0) = M = 3\)。现在他们已经掌握了 \(U\) 和 \(M\)，可以通过插值求出 \(R(x)\) 从而得到 \(R(0) = s = 4\)。

解法二（单多项式方案）

或者，可以构造一个八次多项式（需要 9 个点进行插值），并向每个人类分发 1 个点、向每个霍比特人分发 4 个点、向精灵分发 8 个点、向矮人分发 8 个点。可以看到，如果所有人类达成一致，他们还需要另外 4 个点才能成功插值，而所有其他种族的成员每人至少被分配了 4 个点。此外，其他每个种族合计拥有 8 个点，这意味着如果所有霍比特人、精灵或矮人达成一致，他们只需要额外一个点，而队伍中来自其他种族的任何成员都可以提供该点。另一方面，不满足条件的群体所能获得的最大点数为 8，即来自一名霍比特人和除一人之外的所有人类组成的群体。这不足以完成插值，因此该方案满足要求。

关键洞察是：基于多项式的秘密共享和基于多项式的纠错码，都建立在“对一个底层多项式在许多点上求值，再试图恢复该多项式”这一共同基础之上，因此可以自然地结合起来。

设密码为 \(s\)。军官可以构造一个多项式 \(P(x)\) 使得 \(s = P(0)\)，并把 \((i, P(i))\) 分享给部队里的第 \(i\) 个人。接下来问题是：\(P(x)\) 的次数应该是多少，以及最小的 \(N\) 是多少？

首先，多项式次数 \(d\) 不能小于 \(3\)。因为当 \(d < 3\) 时，\(3\) 个间谍手中的 \(3\) 个点就足以唯一确定 \(P(x)\)（次数 \(< 3\) 的多项式至多有 \(2\) 次，\(3\) 个点可唯一确定它），从而直接得到 \(P(0) = s\)。因此 \(n\)（码字长度，即人数）至少为 \(4\)。

取一个次数为 \(3\) 的多项式 \(P(x)\) 满足 \(s = P(0)\)。现在把 \(3\) 个间谍视作 \(3\) 个一般错误。此时最小的 \(N = 10\)，因为 \(n\)（消息长度，即多项式次数加一）至少为 \(4\)，而一般错误个数 \(k = 3\)，于是“码字”长度为 \(n + 2k = 4 + 2 \cdot 3 = 10\)（在我们的场景里就是人数）。即使这 \(3\) 个间谍就在那 \(10\) 个人当中，并且在自己对应的数值上撒谎，这 \(10\) 个人仍然可以通过 Berlekamp-Welch 算法纠正 \(k = 3\) 个一般错误，从而求出正确的 \(P(x)\)，进而得到 \(P(0) = s\)。

为什么更小的 \(N\) 不行：若 \(N \le 9\)，则总人数不足以容纳“\(4\) 个消息符号 + \(2 \cdot 3 = 6\) 个纠错冗余”，Berlekamp-Welch 算法无法保证纠正 \(3\) 个一般错误；同时，若把次数降到 \(3\) 以下，则 \(3\) 个间谍自己就能唯一确定多项式。因此最小的 \(N\) 是 \(10\)。

替代方案：另一种可行的做法是取 \(P(x)\) 的次数为 \(N - 1\)，并额外加入 \(6\) 个公开点来处理来自间谍的 \(3\) 个一般错误。也就是说，除了各自的 \((i, P(i))\) 之外，每个人还知道另外 \(6\) 个点的取值 \((t+1, P(t+1)), (t+2, P(t+2)), \dots, (t+6, P(t+6))\)，其中 \(t\) 为部队人数。间谍总共能拿到 \(3 + 6 = 9\) 个点，因此次数 \(N-1\) 必须至少为 \(9\)，才能防止间谍仅凭自己手中的点打开保险箱。故最小的 \(N\) 仍为 \(10\)。

(a) 设我们总共发送 \(m\) 个包（\(m\) 待定）。由于至多丢失占比 \(\alpha\) 的包，因此收到的包数至少为 \((1-\alpha)m\)。但为了重构传输所用的多项式，我们至少需要 \(n\) 个包。因此只要 \((1-\alpha)m\ge n\) 就足够了，整理可得 \(m\ge n/(1-\alpha)\)。

(b) 设我们总共发送 \(m=n+2k\) 个包，其中 \(k\) 是我们能防范的错误数。被损坏的包数至多为 \(\alpha m\)，因此需要 \(k\ge \alpha m\)。于是 \(m\ge n+2\alpha m\)，整理可得 \(m\ge n/(1-2\alpha)\)。

注意：当 \(\alpha\ge 1/2\) 时，恢复是不可能的。

(a) 我们可以使用 Berlekamp-Welch 算法。令 \(Q(x)=P(x)E(x)\)。由于至多 1 个错误，\(E(x)\) 为 1 次；由于 \(P(x)\) 为 2 次，\(Q(x)\) 为 3 次。列线性方程组并求解：

\[d=-e\] \[a+b+c+d=3-3e\] \[a+4b+2c+d=0\] \[6a+2b+3c+d=3-e\] \[a+2b+4c+d=0\]

解得 \(Q(x)=x^3+5x^2+5x+4\)，\(E(x)=x-3\)。将 \(Q(x)\) 除以 \(E(x)\) 得 \(P(x)=x^2+x+1\)。因此 Alice 的消息为 \(m_1=1,m_2=1,m_3=1\)，Eve 改变的包的 \(x\) 值为 3。

另解：由于有 5 个点，我们需要找到一个穿过其中 4 个点的 2 次多项式，未被穿过的那个点就是 Eve 改变的包。取点 \((1,3)\)、\((2,0)\)、\((4,0)\)，该多项式在 \(x=2\) 和 \(x=4\) 处为 0，因此为 \(k(x-2)(x-4)=k(x^2+x+1)\pmod 7\)。代入 \((1,3)\) 得 \(k\equiv 1\)，故多项式为 \(x^2+x+1\)。代入 \(x=0\) 得 1，符合；代入 \(x=3\) 得 \(13\equiv 6\not\equiv 1\)，故 \(x=3\) 是被改变的包。Alice 的原始消息为 \(m_1=1,m_2=1,m_3=1\)。

(b) 由于 Bob 知道 Eve 改变了 2 个点，剩下的 3 个点仍在 Alice 用来编码消息的 1 次多项式上。若 Bob 能找到一个穿过其所接收点中至少 3 个点的 1 次多项式，他就能唯一恢复 Eve 的消息。唯一无法唯一确定 Alice 消息的情况是：有两条不同的 1 次多项式都能穿过所接收 5 个点中的 3 个点。

点 \((0,5)\)、\((1,7)\)、\((4,0)\) 已在一条直线上。若 \(x=6\)，则 \((1,7)\)、\((2,6)\)、\((3,5)\) 也在一条直线上。若 \(x=5\)，则 \((0,5)\)、\((2,5)\)、\((3,5)\) 也在一条直线上。若 \(x=9\)，则 \((0,5)\)、\((2,9)\)、\((4,0)\) 落在原始直线上，Bob 可以解码。若 \(x=10\)，则 \((2,10)\)、\((3,5)\)、\((4,0)\) 也在一条直线上。因此当 \(x=6,5,10\) 时，Bob 无法唯一确定 Alice 的消息。

(c) 信道 X 会送达 6 个包，因此我们可以通过它发送一个编码在 5 次多项式上的长度为 6 的消息。若通过信道 X 发送 10 个点，则无论 Bob 收到哪 6 个点，都能重构我们的 5 次多项式。由于信道 Y 有 1 个一般错误，我们只能通过它发送一个编码在 3 次多项式上的长度为 4 的消息。若发送 10 个点，Bob 将收到 6 个点来计算一个具有 1 个一般错误的 4 次多项式，这是可行的。因此，为了发送长度为 9 的消息，我们可以将第 1–6 个字符通过信道 X 发送，第 7–9 个字符通过信道 Y 发送。

另解：Alice 可以插值出一个编码长度为 9 消息的 8 次多项式。她通过信道 X 发送该多项式的 10 个点，并通过信道 Y 发送同一多项式的另外 10 个点。Bob 从信道 X 收到 6 个点，从信道 Y 收到 6 个点（其中 1 个被篡改）。他可以使用 \(n=9\)、\(k=1\) 的 Berlekamp-Welch 算法恢复原始多项式，并通过在相关点求值来提取消息。