Lecture 8: Secret Sharing & Error-Correcting Codes（秘密共享与纠错码）

目录 · ← l8 · l10 →

Lecture 8: Secret Sharing & Error-Correcting Codes（秘密共享与纠错码）

概述

本讲把讲次 7 建立的多项式工具用到两个看似不同、实则同源的问题上：秘密共享 (Secret Sharing) —— 如何把一个秘密拆成 $n$ 份，使任意 $k$ 份能拼回秘密，而任意 $k-1$ 份对秘密一无所知；以及纠错码 (Error-Correcting Codes) —— 如何在有噪声的信道上传输消息，使接收方在部分信息被擦除 (erasure) 或被篡改 (corruption) 之后仍能还原原文。两个问题的共同钥匙只有一句话：次数不超过 $d$ 的多项式由 $d+1$ 个点唯一确定，而少于 $d+1$ 个点则什么都确定不了。本讲主要使用四套技术：正确性靠插值的唯一性；安全性靠「对每个猜测值都能构造出恰好一条相容曲线」的构造性论证；纠错能力靠汉明距离 (Hamming distance) 加三角不等式；而 Berlekamp–Welch 译码把「枚举错误位置」这一指数级搜索转化为解一个线性方程组。本讲也是课程从”数论与密码”过渡到”代数与编码”的收口之处：讲次 9–11 将切换到完全不同的建模语言——图论。

核心概念的直观解释

门限方案（(n,k) threshold scheme）

• 定义：把秘密 $s$ 分配给 $n$ 个参与方，使得 (1) 任意 $k$ 个参与方合起来可以唯一确定 $s$；(2) 任意 $k-1$ 个或更少的参与方合起来不能获得关于 $s$ 的任何信息。第二条中的”任何信息”是信息论意义下的：他们关于 $s$ 的后验分布与先验分布完全相同。
• 直观解释（”它是什么意思？”）：想象一只需要多把钥匙同时插入才能打开的保险箱。$k$ 是”门限”：低于门限什么都做不了，达到门限则一把不多不少刚好够。现实类比是冷战时期的核发射授权——没有任何单个人应该掌握发射码，但也不能要求全体官员都到场，否则在突袭下根本来不及反击。
• 具体示例：$n=5,k=3$ 时，”官员 1、3、4 三人凑齐”能算出秘密；”官员 1、3 两人凑齐”无论怎么交换信息、怎么联合计算，都与单独一个人知道的完全一样多。注意 (2) 比”算不出来”强得多：它还包括”看不出 $s$ 是奇数还是偶数”“看不出 $s$ 是否素数”“看不出 $s$ 的最低有效位”等等。

Shamir 秘密共享（Shamir’s Secret Sharing）

• 定义：设 $q$ 是大于 $n$ 且大于 $s$ 的素数，在有限域 (finite field) $GF(q)$（也写作 $\mathbb{F}q$）上工作。随机选取一个次数恰好为 $k-1$ 的多项式 \(P(x) = s + a_1 x + a_2 x^2 + \cdots + a_{k-1}x^{k-1} \pmod q,\) 其中常数项固定为秘密 $P(0)=s$，而 $a_1,\dots,a{k-1}$ 从 $GF(q)$ 中独立均匀随机抽取。第 $i$ 个参与方拿到份额 (share) $(i, P(i))$，$i=1,2,\dots,n$。
• 直观解释（”它是什么意思？”）：秘密藏在曲线的截距上，而 $k-1$ 个随机系数是”陪衬噪声”。$k$ 个点像 $k$ 颗钉子，把曲线钉死，截距随之暴露；$k-1$ 颗钉子钉不住一条曲线——它还能上下自由摆动，而摆动的一个自由度恰好就是截距。每个随机系数都是一件”牺牲品”：它主动吸收掉一部分不确定性，让秘密本身保持未知。另一种等价的说法是线性代数的：$k-1$ 个方程解不出 $k$ 个未知数，总有一个自由度；刻意保留的那个自由度就是秘密。
• 具体示例：$q=11,n=5,k=3,s=5$，取 $P(x)=5+2x+3x^2 \pmod{11}$。份额是 $(1,10),(2,10),(3,5),(4,6),(5,2)$。任意 3 份都能反解出 $P(0)=5$；任意 2 份（比如 $(1,10)$ 与 $(3,5)$）对 $s^{\prime}=0,1,\dots,10$ 这 11 个猜测值都各自对应一条独有的相容抛物线，因此这 2 份数据与 $s$ 的取值在信息论上完全独立。

擦除错误（erasure error）与一般错误（general error）

• 定义：擦除错误指某些”包”在传输中丢失，接收方知道是哪些位置丢了（包有编号头部）；一般错误指某些字符被篡改了，接收方收到的字符数与发送的一样多，但不知道哪些位置被改。
• 直观解释（”它是什么意思？”）：前者像寄一摞明信片，路上丢了两张，收件人一看编号就知道第 2、6 张没到；后者像有人偷偷把明信片上的字改了，收件人手上张数齐全，却分不清哪几行是假的。显然”不知道错误位置”要困难得多。
• 具体示例：$n$ 个字符的消息要防 $k$ 个丢失，只需多发 $k$ 个冗余字符（共 $n+k$ 个）；但要防 $k$ 个篡改，必须多发 $2k$ 个冗余字符（共 $n+2k$ 个）。这个两倍代价不是实现上的偷懒，而是距离理论给出的硬下界（见定理 8.3 与反例）。

码字、消息、以及”冗余”的确切含义

• 定义：消息 (message) 是用户交给我们、不一定含冗余的原始数据串；码字 (codeword) 是实际被发送、按构造含有冗余的串。编码 (encoding) 是一张从消息集合到码字集合的单射。
• 直观解释（”它是什么意思？”）：消息是”你想说的话”，码字是”你实际写在信纸上的字”。多出来的部分是故意的重复，专门用来在丢字或被改字时救场。
• 具体示例：$GF(7)$ 上消息 $(1,1,1)$（3 个符号）对应码字 $(3,0,6,0,3)$（5 个符号），冗余 2 个符号，可抗 $e=1$ 个一般错误。

汉明距离（Hamming distance）与最小距离（minimum distance）

• 定义：对两个长度 $L$ 的字符串 $\vec{s}=(s_1,\dots,s_L)$ 与 $\vec{r}=(r_1,\dots,r_L)$， \(d(\vec{s},\vec{r}) = \sum_{i=1}^{L} \mathbf{1}(r_i \neq s_i),\) 即两个串在多少个坐标上不同（$\mathbf{1}(\cdot)$ 是”条件成立取 1，否则取 0”的指示函数）。所有码字两两距离中的最小值称为该码的最小距离 \(d_{\min} = \min_{\vec m \neq \vec m^{\prime}} d\big(\vec c(\vec m), \vec c(\vec m^{\prime})\big).\)
• 直观解释（”它是什么意思？”）：把每个码字想象成空间中的一颗星球，距离就是”改几个字符能从一颗星球飞到另一颗”。星球之间离得越远，噪声要”漂移”很久才能把人骗到隔壁星球。$d_{\min}=1$ 意味着原始消息集合毫无防护；$d_{\min}$ 越大防护越强。汉明距离满足三条公理：非负性、对称性、三角不等式 $d(\vec a,\vec c)\le d(\vec a,\vec b)+d(\vec b,\vec c)$——第三条第是纠错能力证明的全部依据。
• 具体示例：消息集合 $\{00,01,10,11\}$ 的最小距离是 1（$00$ 与 $01$ 只差一位）——收到 $0?$ 无法判断原来是 $00$ 还是 $01$，零防护。对比重复码 $\{000,111\}$，最小距离是 3：收到 $001$ 可以断定原码字是 $000$（距离 1），因为到 $111$ 的距离是 2，更远。

Reed–Solomon 码（Reed–Solomon code）

• 定义：取素数 $q$，消息为 $\vec m=(m_0,m_1,\dots,m_{k-1})\in GF(q)^k$，把它解释为次数 $<k$ 的多项式 $P(x)=m_0+m_1x+\cdots+m_{k-1}x^{k-1}$ 的系数表示 (coefficient representation)。选定 $n$ 个互不相同的求值点 $\alpha_1,\dots,\alpha_n \in GF(q)$，码字就是 $P$ 的值表示 (value representation) \(\vec c(\vec m) = \big(P(\alpha_1), P(\alpha_2), \dots, P(\alpha_n)\big).\) 发送的是 $\vec c$，不是 $\vec m$。
• 直观解释（”它是什么意思？”）：编码不过是”把系数形式的曲线画在 $n$ 个刻度上”，解码则是”用一堆点重新拟合曲线”。如果只有一两个点被涂歪，曲线整体形状仍然明显可辨——这正是冗余的来源。系数表示与值表示的互相转换（前者靠求值，后者靠插值）是讲次 7 已经建立好的两种视角。
• 具体示例：$GF(7)$ 上取 $k=3$、求值点 $1,2,3,4,5$，消息 $(1,1,1)$ 即 $P(x)=1+x+x^2$，求值得码字 $(3,0,6,0,3)$（检验 $P(3)=1+3+9=13\equiv 6$）。

错误定位多项式（error-locator polynomial）

• 定义：设实际发生错误的位置集合为 $\{e_1,\dots,e_t\}$（$t\le e$），定义 \(E(x) = \prod_{j=1}^{t}(x-e_j).\) 它是次数恰为 $t$ 的多项式，根恰好是全部错误位置。在算法中我们把它的次数统一写成 $e$，即取首一形式 $E(x)=x^{e}+b_{e-1}x^{e-1}+\cdots+b_1x+b_0$；当 $t<e$ 时再乘以任意一个 $e-t$ 次首一多项式补足次数（这不影响任何论证，只影响”解是否唯一”）。
• 直观解释（”它是什么意思？”）：它是错误的”通缉令”——虽然接收方还不知道谁犯了错，但可以把这个通缉令符号化地写出来，把它当成未知对象一起列进方程。解方程的过程会顺便把通缉令上的名字填上。这就是 Berlekamp–Welch 的精妙之处：不求位置，把位置当未知数解。
• 具体示例：在 $GF(7)$ 上若只在第 1 个坐标出错，则 $E(x)=x-1=x+6$，$E(1)=0$，而 $E(2)=1$、$E(5)=4$ 都非零。

Berlekamp–Welch 译码（Berlekamp–Welch decoding）

• 定义：给定 $n$ 个接收值 $r_1,\dots,r_n$，其中最多 $e$ 个被篡改，且 $n \ge k+2e$。构造辅助多项式 $Q(x) := P(x)E(x)$，其次数 $\le (k-1)+e = k+e-1$。对每个 $i$ 列出方程 \(Q(i) = r_i E(i), \qquad i=1,2,\dots,n,\) 这是关于 $Q$ 与 $E$ 的系数的线性方程组：$k+e$ 个未知数（$Q$ 的系数）加 $e$ 个未知数（$E$ 的 $b_0,\dots,b_{e-1}$，首项系数已归一为 1），合计 $k+2e \le n$ 个未知数，$n$ 条方程。解出后用多项式长除法还原 $P(x)=Q(x)/E(x)$，并对错误位置用 $P$ 重新求值。
• 直观解释（”它是什么意思？”）：只要 $i$ 没出错，$P(i)=r_i$，于是 $Q(i)=P(i)E(i)=r_iE(i)$；只要 $i$ 出错了，$E(i)=0$，于是左右两边都是 0。无论出错与否，这个方程都成立——这就是把未知的错误位置”吸收”进方程组的技巧。原来要靠枚举 $\binom{n}{e}$ 种错误位置（指数级），现在只需解一次线性方程组（多项式时间）。
• 具体示例：见后文完整算例——$GF(7)$、$k=3$、$n=5$、$e=1$、接收串 $(2,0,6,0,3)$ 时解出 $Q=x^3+6$、$E=x+6=x-1$，长除法得 $P=x^2+x+1$，并定位出错误在第 1 位。

完整证明与推导（核心）

定理 8.1（Shamir 方案的正确性）：设 $q>n$ 为素数，$s\in GF(q)$，$P$ 是 $GF(q)$ 上次数为 $k-1$、常数项为 $s$ 的多项式。任意 $k$ 个参与方 $i_1<\dots<i_k$（$1\le i_j\le n$）出示各自的份额 $(i_j, P(i_j))$，则可从这些份额唯一确定 $P$，从而恢复 $s=P(0)$。

证明策略：直接证明，并引用讲次 7 的插值唯一性（Property 2）。之所以能直接引用，是因为 $GF(q)$ 是一个域 (field)：加、减、乘以及”除以非零元”四条运算都封闭；而讲次 7 关于两个多项式性质的证明只用到这四条运算。

逐步推导：

1. 设 $Q(x)$ 是任意一个次数 $\le k-1$ 且满足 $Q(i_j)=P(i_j)$（$j=1,\dots,k$）的多项式。依据：定义。
2. 令 $D(x) := P(x)-Q(x)$。依据：代数运算。
3. $D$ 的次数 $\le k-1$，且 $D(i_j)=P(i_j)-Q(i_j)=0$ 对 $j=1,\dots,k$ 成立，即 $D$ 至少有 $k$ 个互不相同的根。依据：第 1、2 步与”根”的定义。
4. 由讲次 7 的 Property 1（非零的次数 $d$ 多项式至多有 $d$ 个根）：若 $D$ 非零，则其次数至少为 $k$，与第 3 步矛盾。故 $D\equiv 0$，即 $Q=P$。依据：Property 1。
5. 于是过这 $k$ 个点的次数 $\le k-1$ 多项式唯一，就是 $P$。依据：第 4 步。
6. 具体地，参与方可以用 Lagrange 插值显式写出 \(P(x)=\sum_{j=1}^{k} P(i_j)\,\Delta_j(x),\qquad \Delta_j(x)=\prod_{\ell\neq j}\frac{x-i_\ell}{i_j-i_\ell},\) 其中每个分母 $i_j-i_\ell \not\equiv 0 \pmod q$（各 $i$ 互不相同），故其在 $GF(q)$ 中的乘法逆元存在。依据：讲次 7 的 Lagrange 插值公式 + 讲次 5 的逆元存在性（$q$ 为素数 $\Rightarrow$ 每个非零元可逆）。
7. 令 $x=0$ 得 $s=P(0)=\sum_{j=1}^{k} P(i_j)\Delta_j(0)$，秘密被唯一恢复。依据：第 5、6 步。

【证明机制解说】：整个正确性的重量全部压在”次数 $\le k-1$ 的非零多项式至多 $k-1$ 个根”这一条上。$k$ 个点提供了 $k$ 个约束，超过任何非零低次多项式所能拥有的根数上限，于是”两条候选曲线之差”这条曲线被逼成零曲线。这就是所谓的“自由度刚好用完”：$k$ 个未知系数被 $k$ 个方程锁死，没有留下一丝摇摆空间。

反例（条件不可省）：如果只有 $k-1$ 个点，唯一性立即崩塌。在 $GF(11)$ 上取 $k=3$、份额 $(1,10)$ 与 $(3,5)$：对 $s^{\prime}=0$，经过 $(0,0),(1,10),(3,5)$ 的插值多项式是 $P^{\prime}(x)=5x+5x^2$；对 $s^{\prime}=7$，经过 $(0,7),(1,10),(3,5)$ 的是 $P^{\prime}(x)=7+3x$。两条曲线都过这两个已知点，却给出不同的秘密——所以 $k-1$ 个点确实无法确定 $P(0)$。更一般地（见定理 8.2），每个 $s^{\prime}\in GF(11)$ 都恰好对应一条相容曲线。

定理 8.2（Shamir 方案的安全性：信息论意义下的零泄露）：在 Shamir 方案中，任意 $k-1$ 个（或更少）参与方的份额与秘密 $s$ 在信息论上相互独立。更精确地说：对任意固定的份额集合 $S=\{(i_1,y_1),\dots,(i_{k-1},y_{k-1})\}$（$i_j$ 互不相同且落在 $1,\dots,n$ 内）以及任意猜测值 $s^{\prime}\in GF(q)$，都存在唯一一个次数 $\le k-1$ 的多项式 $P^{\prime}$，使得 \(P^{\prime}(0)=s^{\prime} \quad\text{且}\quad P^{\prime}(i_j)=y_j \ \ (j=1,\dots,k-1).\)

证明策略：构造性证明（存在性）+ 引用唯一性。策略选择的关键在于：要证”得不到任何信息”，不能只说”算不出来”（那是计算复杂度，不是信息论事实），必须证明每一种可能的秘密值都与其他观测数据一样兼容。所以要为每个 $s^{\prime}$ 显式造出一条曲线，并数清楚候选曲线的总数没有减少。

逐步推导：

1. 固定 $S$，另加一个虚拟的”第 $k$ 个点” $(0,s^{\prime})$。依据：构造。
2. 这 $k$ 个点的横坐标 $0,i_1,\dots,i_{k-1}$ 两两不同（因为 $i_j\ge 1$ 且各 $i_j$ 互不相同）。依据：方案设定 $1\le i_j\le n$。
3. 由讲次 7 的 Property 2，存在唯一的次数 $\le k-1$ 的多项式 $P^{\prime}$ 经过这 $k$ 个点。依据：插值唯一性。
4. $P^{\prime}$ 与实际被使用的曲线 $P$ 在参与方所知的 $k-1$ 个点上取值完全重合：$P^{\prime}(i_j)=y_j=P(i_j)$。依据：第 1、3 步。
5. 对每个 $s^{\prime}\in GF(q)$（共 $q$ 个值）执行第 1–4 步，得到 $q$ 条曲线。它们两两不同：若 $s^{\prime}\neq s^{\prime\prime}$，则 $P^{\prime}$ 与 $P^{\prime\prime}$ 在 $x=0$ 处取值不同，故不是同一个多项式。依据：第 3、4 步。
6. 因此，参与方观测到的 $k-1$ 个份额与 $q$ 个候选秘密值中的每一个都同等相容：数据无法排除任何一个候选，也无法偏好任何一个候选。用条件概率的语言（讲次 17–18）说，若秘密的先验是均匀的，则 \(\Pr[\text{秘密}=s^{\prime} \mid \text{观测到 } S]=\frac{1}{q}=\Pr[\text{秘密}=s^{\prime}],\) 后验等于先验，即条件分布与边缘分布相同——按定义这就是相互独立，信息量为 $0$ 比特。依据：第 4、5 步 + 条件概率定义。
7. 特别地，攻击者无法判断 $s$ 的奇偶性、是否为素数、最低有效位、是否被某个数整除——因为这些量都是 $s$ 的确定性函数，而 $s$ 的后验分布是均匀的。依据：第 6 步。
8. 对比第 $k$ 个参与方加入时：候选集合从 $q$ 个坍缩到恰好 1 个，信息量从 $0$ 比特跃升为满额 $\log_2 q$ 比特。这个”突变”正是门限之所以尖锐的原因。依据：第 3、5 步。

【证明机制解说】：这个证明的”灵光一现”是把”不知道”翻译成”兼容性对称“。直觉说法是”$k-1$ 个点钉不住曲线”，而严格的数学化做法是：把待猜的秘密当作第 $k$ 个点，然后求助于插值的存在唯一性，得到一一对应 \(GF(q)\text{ 中的 }q\text{ 个秘密值}\;\longleftrightarrow\;q\text{ 条相容曲线}\;\longleftrightarrow\;q\text{ 个候选"值表示"}.\) 如果可能候选只有 3 个而不是 $q$ 个，攻击者就获得了约 $\log_2(q/3)$ 比特信息；正因为候选数恰为 $q$（没有变少），信息量才恰好是 $0$ 比特。这也顺带解释了为什么必须工作在有限域上：只有在有限域里候选数才是有限的 $q$ 个，才能精确地断言”候选数没有减少”；若在实数域上做同样的方案，候选曲线有无限多条，”候选数是否减少”就无法量化。此外，有限域保证所有算术是精确整数运算，不会像浮点插值那样出现数值不稳定。

定理 8.3（距离 → 检错、纠错、纠擦除能力）：设某编码方案的最小距离为 $d$，记 $t=\lfloor (d-1)/2\rfloor$。则： (a) 若传输中被修改的坐标数 $\le t$，接收方可以唯一地恢复原码字（纠错能力）； (b) 若传输中被修改的坐标数 $\le d-1$，接收方可以检测出“出了错”（检错能力）； (c) 若被擦除的坐标数 $\le d-1$，接收方可以唯一地恢复原码字（抗擦除能力）。

证明策略：反证法 + 汉明距离的三角不等式。核心是”球不相交”。

逐步推导（(a) 纠错）：

1. 设接收串为 $\vec r$，真实码字为 $\vec c$，且 $d(\vec r,\vec c)\le t$。依据：问题设定。
2. 反设还存在另一个不同的码字 $\vec c^{\prime}$ 也满足 $d(\vec r,\vec c^{\prime})\le t$。依据：反证假设。
3. 由三角不等式，$d(\vec c,\vec c^{\prime})\le d(\vec c,\vec r)+d(\vec r,\vec c^{\prime})\le t+t=2t$。依据：三角不等式与第 1、2 步。
4. 又由 $t=\lfloor (d-1)/2\rfloor$ 得 $2t\le d-1<d$。依据：取整估计。具体地：若 $d=2e+1$，则 $t=e$，$2t=2e=d-1$；若 $d=2e$，则 $t=e-1$，$2t=2e-2=d-2$。
5. 第 3、4 步合起来给出 $d(\vec c,\vec c^{\prime})<d$，与 $d$ 是最小距离（任意两个不同码字的距离都 $\ge d$）矛盾。依据：最小距离的定义。
6. 故这样的 $\vec c^{\prime}$ 不存在，$\vec c$ 是唯一与 $\vec r$ 距离 $\le t$ 的码字——”最近码字译码 (nearest-codeword decoding)”的输出唯一，且正是真实码字。依据：第 5 步。

逐步推导（(b) 检错）：

1. 设 $d(\vec r,\vec c)\le d-1$，且反设 $\vec r$ 本身恰好也是一个码字 $\vec c^{\prime}$（即 $d(\vec r,\vec c^{\prime})=0$）。依据：反证假设。
2. 则 $d(\vec c,\vec c^{\prime})\le d(\vec c,\vec r)+d(\vec r,\vec c^{\prime})\le (d-1)+0=d-1<d$。依据：三角不等式。
3. 与最小距离定义矛盾。故 $\vec r$ 不可能是合法码字（除非真的没出错）。接收方一旦发现”收到的串不是合法码字”，就能断定有错。依据：第 2 步。

逐步推导（(c) 抗擦除）：

1. 设擦除掉 $\ell\le d-1$ 个坐标后，有两个不同码字 $\vec c\neq\vec c^{\prime}$ 都与剩余数据相容。依据：反证假设。
2. 相容意味着它们在所有未被擦除的坐标上取值相同，所以它们不同的坐标必然都落在被擦除的 $\ell$ 个位置里。依据：相容的定义。
3. 于是 $d(\vec c,\vec c^{\prime})\le \ell\le d-1<d$，与最小距离定义矛盾。依据：第 2 步。
4. 故相容码字唯一。依据：第 3 步。
5. 反过来这个界也是紧的：若 $\ell\ge d$，则可取一对距离恰为 $d$ 的码字，擦掉那 $d$ 个差异坐标，剩余数据同时与两者相容，译码必然歧义。依据：最小距离的定义与紧性构造。

【证明机制解说】：这就是”汉明球“图像：以每个码字为球心、半径 $t$ 画球（球内是全部与球心距离 $\le t$ 的串）。若两个球有公共点 $\vec r$，则两个球心的距离 $\le 2t<d$，与最小距离冲突。所以半径 $t=\lfloor (d-1)/2\rfloor$ 的球两两不相交；接收串落在哪个球里就判给哪个球心，绝不会撞车。反过来半径再大一点球就必然重叠，纠错就不再唯一。这也立刻给出三个能力的”汇率”：$d$ 个距离单位可换 $d-1$ 个检错、$\lfloor (d-1)/2\rfloor$ 个纠错、$d-1$ 个纠擦除。

反例（条件不可省）：$d=2$（例如 $GF(7)$ 上长度 4、$k=3$ 的 RS 码，或弱化的重复码）时 $t=\lfloor 1/2\rfloor=0$：一个错误都纠不了。接收串 $\vec r=(0,1)$ 与 $\vec c=(0,0)$、$\vec c^{\prime}=(1,1)$ 的距离都是 1，解码器彻底茫然。这正是为什么”$n=k+2e-1$ 就够”的猜想是错的：把码长从 $n+2e$ 降到 $n+2e-1$，最小距离从 $2e+1$ 降到 $2e$，纠错半径就从 $e$ 掉到 $e-1$。

定理 8.4（Reed–Solomon 码的最小距离）：取码字长度 $n$、消息长度 $k$（即多项式次数 $<k$）、求值点 $\alpha_1,\dots,\alpha_n$ 互不相同，则 $d_{\min}=n-k+1$。

证明策略：双向夹逼。下界（$\ge$）用反证法 + Property 1；上界（$\le$）用显式构造一对距离恰为 $n-k+1$ 的码字。

逐步推导（下界）：

1. 取两个不同的消息 $\vec m\neq\vec m^{\prime}$，对应多项式 $P\neq P^{\prime}$，次数都 $\le k-1$。依据：编码是单射，且消息 $\leftrightarrow$ 系数一一对应。
2. $D(x)=P(x)-P^{\prime}(x)$ 是非零多项式，次数 $\le k-1$。依据：$P\neq P^{\prime}$，差的次数不超过两者次数之最大值。
3. 由 Property 1，$D$ 在 $GF(q)$ 中至多有 $k-1$ 个根。依据：讲次 7 的 Property 1。
4. 因此 $P(\alpha_i)\neq P^{\prime}(\alpha_i)$ 至少在 $n-(k-1)=n-k+1$ 个求值点上成立（至多有 $k-1$ 个求值点可能”撞车”）。依据：第 3 步 + $n$ 个求值点互不相同。
5. 即 $d(\vec c(\vec m),\vec c(\vec m^{\prime}))\ge n-k+1$ 对任意一对不同消息成立，故 $d_{\min}\ge n-k+1$。依据：最小距离定义。

逐步推导（上界）：

1. 构造 $P(x) := \prod_{j=1}^{k-1}(x-\alpha_j)$，其系数取自 $GF(q)$，次数恰为 $k-1\le k-1$，故它是合法消息对应的多项式；再取 $P^{\prime}(x):=0$（即全零消息）。依据：构造（注意 $k=1$ 时该乘积为空积，取 $P(x)\equiv 1$，此时 $n-k+1=n$，与第 8 步结论一致）。
2. $P$ 与 $P^{\prime}$ 在每个 $\alpha_j$（$j\le k-1$）处取值相同：$P(\alpha_j)=0=P^{\prime}(\alpha_j)$。依据：第 6 步。
3. 而对 $j>k-1$，$\alpha_j\notin\{\alpha_1,\dots,\alpha_{k-1}\}$，故 $P(\alpha_j)\neq 0=P^{\prime}(\alpha_j)$——两者不同。所以在 $n$ 个坐标中恰有 $n-(k-1)=n-k+1$ 个坐标不同，即 \(d\big(\vec c(\vec m_P),\vec c(\vec m_{P^{\prime}})\big)=n-k+1 .\) 依据：第 6、7 步。
4. 最小距离是最小的那一对，故 $d_{\min}\le n-k+1$。依据：第 8 步。
5. 第 5 步与第 9 步合起来：$d_{\min}=n-k+1$。依据：双向夹逼。

与官方 Note 参数化的对照：官方记消息长 $n_{\!o}$、码字长 $n_{\!o}+2k_{\!o}$、要纠 $k_{\!o}$ 个错误，对应本笔记的 $k=n_{\!o}$、$n=n_{\!o}+2k_{\!o}$、$e=k_{\!o}$。于是 $d_{\min}=n-k+1=2k_{\!o}+1$，与官方 Note 的定理（”把 $n$ 个消息字符编成 $n+2k$ 长码字的 RS 码，最小距离为 $2k+1$”）完全一致。由定理 8.3(a)，$2k_{\!o}+1$ 的距离恰好能纠 $\lfloor 2k_{\!o}/2\rfloor=k_{\!o}$ 个错误，冗余量分毫不差。

【证明机制解说】：这个定理的全部魔法只有一句：“两个不同的低次多项式不能在许多点上相等”。次数 $<k$ 的曲线彼此至多相交 $k-1$ 次，所以只要采样点够多，任意两条不同曲线对应的码字就必然在至少 $n-k+1$ 个刻度上分歧。第 6–8 步那个”让 $P^{\prime}$ 取零多项式、让 $P$ 恰好在 $k-1$ 个求值点取零”的构造说明这个界能被达到；而定理断言的是最坏的那对也有 $n-k+1$。这正是 RS 码被称为 MDS 码 (Maximum Distance Separable，可达最大距离可分码) 的原因：在给定 $n$ 与 $k$ 时，没有任何码能做得更好（这是 Singleton 界 $d\le n-k+1$ 的等号情形）。

定理 8.5（Berlekamp–Welch 译码的正确性）：工作于 $GF(q)$，$q>n$。设消息长度 $k$、码字长度 $n$、$n\ge k+2e$。接收值为 $r_1,\dots,r_n$，真实码字来自次数 $<k$ 的多项式 $P$，且实际错误数 $t\le e$。设 $(Q^{\prime},E^{\prime})$ 是线性方程组 $Q(i)=r_iE(i)$（$i=1,\dots,n$）的任意一组解，其中 $Q^{\prime}$ 次数 $\le k+e-1$、$E^{\prime}$ 是首一且次数恰为 $e$ 的非零多项式。则 $E^{\prime}$ 整除 $Q^{\prime}$，且 $Q^{\prime}/E^{\prime} = P$。

证明策略：先说明方程组的相容性（显式给出一组解），再证明商唯一。商唯一的关键杠杆是”两条次数都 $\le n-1$ 的多项式若在 $n$ 个点上相等则恒等”——这是讲次 7 唯一性定理的第三次露面，只不过这次用在乘积 $Q^{\prime}E$ 与 $QE^{\prime}$ 上。得到恒等之后才敢做除法。

逐步推导：

1. （相容性）令 $E(x)=\prod_{j=1}^{t}(x-e_j)\cdot g(x)$，其中 $g$ 是任意的次数为 $e-t$ 的首一多项式（$t=e$ 时取 $g\equiv 1$；$t<e$ 时可取 $g(x)=x^{\,e-t}$），这样 $E$ 是首一 $e$ 次多项式。再令 $Q(x)=P(x)E(x)$，其次数 $\le (k-1)+e=k+e-1$。依据：构造。
2. 对每个 $i$：若 $i$ 不是错误位置，则 $r_i=P(i)$，于是 $Q(i)=P(i)E(i)=r_iE(i)$；若 $i$ 是错误位置，则 $E(i)=0$，于是 $Q(i)=P(i)\cdot 0=0=r_i\cdot 0=r_iE(i)$。两种情况都满足方程。依据：$E$ 的根恰好包含全部错误位置。
3. 故第 1 步的 $(Q,E)$ 是一组解，方程组必有解（相容），解集非空。依据：第 2 步。
4. （规模核算）未知数个数：$Q$ 的系数 $a_0,\dots,a_{k+e-1}$ 共 $k+e$ 个；$E$ 的系数 $b_0,\dots,b_{e-1}$ 共 $e$ 个（$x^e$ 的系数固定为 1，不是未知数）。合计 $k+2e$ 个；方程数 $n$。由条件 $n\ge k+2e$，未知数不多于方程数。依据：定义 + 条件。
5. 设 $(Q^{\prime},E^{\prime})$ 是任意一组解，于是 $Q^{\prime}(i)=r_iE^{\prime}(i)$ 对所有 $i$ 成立；同时 $Q(i)=r_iE(i)$ 也成立。依据：第 2 步与”$(Q^{\prime},E^{\prime})$ 是解”。
6. 把第一式乘 $E(i)$、第二式乘 $E^{\prime}(i)$，两边都等于 $r_iE(i)E^{\prime}(i)$，故 \(Q^{\prime}(i)E(i)=Q(i)E^{\prime}(i),\qquad i=1,2,\dots,n.\) 依据：代数运算（$GF(q)$ 中乘法交换）。
7. 考虑多项式 $A(x):=Q^{\prime}(x)E(x)$ 与 $B(x):=Q(x)E^{\prime}(x)$。次数上：$\deg A\le (k+e-1)+e=k+2e-1\le n-1$，同理 $\deg B\le n-1$。依据：次数相加 + 条件 $n\ge k+2e$。
8. $A-B$ 的次数 $\le n-1$，却在 $n$ 个互不相同的点 $1,2,\dots,n$ 上取零（第 6 步），故 $A-B$ 至少有 $n$ 个根；由 Property 1（次数 $\le n-1$ 的非零多项式至多 $n-1$ 个根）得 $A-B\equiv 0$，即 \(Q^{\prime}(x)E(x)=Q(x)E^{\prime}(x)\quad\text{对一切 }x\in GF(q).\) 依据：讲次 7 的 Property 1。
9. 代入 $Q=P\cdot E$：$Q^{\prime}(x)E(x)=P(x)E(x)E^{\prime}(x)$。移项得 $E(x)\big(Q^{\prime}(x)-P(x)E^{\prime}(x)\big)=0$。依据：代数运算。
10. $GF(q)$ 上的多项式环是整环 (integral domain)——两个非零多项式之积非零（没有零因子）——且 $E$ 首一故非零，于是由消去律得 \(Q^{\prime}(x)-P(x)E^{\prime}(x)\equiv 0,\qquad\text{即}\quad Q^{\prime}(x)=P(x)E^{\prime}(x).\) 依据：整环消去律。
11. 第 10 步同时说明 $E^{\prime}$ 整除 $Q^{\prime}$，且 $Q^{\prime}(x)/E^{\prime}(x)=P(x)$。依据：整除的定义。
12. 于是无论线性方程组给出哪一组解，长除法 $Q^{\prime}/E^{\prime}$ 得到的一定是 $P$；再用 $P(i)$ 覆盖 $r_i$，即得无错的原消息。依据：第 11 步 + 定理 8.4 的编码定义。

【证明机制解说】：官方 Note 提出的疑问是”方程组会不会有假解 (spurious solution)”。第 8 步是整条链子的关键关节：“$n$ 个点锁死次数 $\le n-1$ 的多项式”。注意第 8 步的结论比”在某 $n$ 个点上取值相等”强得多——它说 $Q^{\prime}E$ 与 $QE^{\prime}$ 作为多项式恒等。只有升级到恒等，第 10 步才敢做除法。同时也要看清定理的边界：它只保证商唯一，不保证 $(Q^{\prime},E^{\prime})$ 唯一。当 $t<e$ 时（尤其当根本没有错误时），$E$ 可以乘上任意补次因子，解构成一整族；但每一族成员的商都等于同一个 $P$。

反例（条件 $n\ge k+2e$ 不可省）：在 $GF(7)$ 上取 $k=3$、$e=1$、$n=k+2e-1=4$，求值点 $1,2,3,4$。取两条消息 \(P_0(x)=0\quad(\text{码字 }0,0,0,0),\qquad P_1(x)=x^2-3x+2\equiv x^2+4x+2 \pmod 7 .\) $P_1$ 的码字为 $(P_1(1),P_1(2),P_1(3),P_1(4))=(0,0,2,6)$，与 $P_0$ 的码字距离为 2（正是 $n-k+1=2$）。现在令接收串 $\vec r=(0,0,2,0)$： \(d(\vec r,\vec c_0)=1\le e=1,\qquad d(\vec r,\vec c_1)=1\le e=1 .\) 两个码字都落在半径 1 的纠错球内，译码结果不唯一：$P(0)=0$ 与 $P(0)=2$ 两个秘密都说得通。这正说明”$n<k+2e$ 时无法唯一译码”，冗余必须加倍。同样地，$k=1,e=1,n=1$（码字长 2）时码字为 $(m,m)$，距离 2，接收串 $(0,1)$ 与 $(0,0)$、$(1,1)$ 的距离都是 1，同样歧义。

与经典问题的联系

问题一：核发射授权（秘密共享的原始动机） 20 世纪 50–60 年代，美国总统艾森豪威尔批准了在极端紧急情况下由高级军官动用核武器的指令。这里的关键约束是双重的：既不能让任何一个人单独掌握发射码，也不能要求所有官员都到场（否则在突袭下无法及时反击）。数学建模：设官员数 $n$、门限 $k$，秘密 $s$ 是发射码（$GF(q)$ 中的一个数，$q>s$ 且 $q>n$）。方案设计即 Shamir 方案：随机取 $a_1,\dots,a_{k-1}$，公开”曲线次数为 $k-1$”这一事实，给第 $i$ 人发 $P(i)$，销毁全部 $a_j$。正确性由定理 8.1 保证（$k$ 人 Lagrange 插值 $\to P(0)=s$）；安全性由定理 8.2 保证（$k-1$ 人的后验分布等于先验）。今日的同类应用包括密钥托管 (key escrow)、多重签名钱包、公司主密钥分权保管、以及安全多方计算 (secure multiparty computation) 中的输入分片。

问题二：从”完整性/认证”转向”冗余/容错”——与 RSA 的分工 讲次 6 的 RSA 解决的是机密性（别人看不懂）与完整性/认证（别人改不了而不被发现，靠哈希与签名）。本讲解决的是另一类问题：我不阻止你改，但我改得回来。二者的分工是密码学与编码理论的分工：

• RSA 假设信道上的对手有计算能力但无无穷算力，用计算困难性换取安全；
• 纠错码假设信道会无心或有意地篡改至多 $e$ 个符号，用冗余换取容错，并且这个容错是无条件的——定理 8.3 与 8.4 不依赖任何计算假设，连算力无限的对手也无法击穿。

一个典型的真实系统会两者并用：先用 RSA 签名保证”这是真的发送者”（认证），再用 RS 码保证”即使路上被划伤 30% 也能读出”（容错）。

问题三：真实世界里的 Reed–Solomon 码

• 光盘与二维码：CD/DVD/Blu-ray 与 QR 码都用 RS 码对抗划痕、污渍与手指印。QR 码的四个纠错等级 L/M/Q/H 分别能恢复约 7%/15%/25%/30% 的码字，物理上等价于选择不同的 $e$。
• 深空与卫星通信：Voyager 1/2 的图片传输用了与卷积码级联的 RS 码；卫星电视、DVB 标准、DSL 与电缆调制解调器均含 RS 码。经典参数 RS(255,223) 在 $GF(2^8)$ 上工作：码字 255 字节、消息 223 字节、最小距离 33，可纠 $\lfloor 32/2\rfloor=16$ 个字节错误。
• 数据中心与分布式存储：把文件切成 $k$ 块并生成 $n-k$ 块冗余（RS 纠删码），任意 $k$ 块即可重建（即本讲的擦除情形），比三副本方案节省大量存储。Facebook 的 f4 系统、Azure 的 LRC 都是这类设计。
• RAID-6 与并行计算：双校验盘本质上是一个允许两块”擦除”的编码；RS 码还被用于加速并行计算中的”慢节点 (straggler)”容错。
• 二维码的实际编码流程：数据字节 $\to$ RS 码字 $\to$ 按掩模图案铺到方阵上。解码时先读定位图形，再按 Reed–Solomon 纠错；若错误数超过纠错能力，二维码会直接报告”无法识别”而不是给出错误结果——这正是定理 8.3(b) 的检错能力在起作用。

数值对照（本讲算例与真实参数的关系）：本笔记用 $GF(7)$、$GF(11)$ 只是为了能手算，所有结构在 $GF(2^8)$ 或 $GF(2^{32})$ 上一字不改。唯一变化是”逆元怎么算”：小域可以试除或查表，大域用扩展欧几里得算法（讲次 5）。条件 $q>n+2e$ 在真实系统中从来不是瓶颈：$n$ 最大不过几千，$q=2^8=256$ 或 $2^{32}$ 都远远够用。注意：$GF(2^{32})$ 是一个域但不是 $\mathbb{Z}_{2^{32}}$；直接对 $2^{32}$ 取模的算术会失去域结构（$2^{32}$ 不是素数），讲次 7 的 Property 1 会失效——真实实现使用的是多项式基下的 $GF(2^{32})$ 算术，这属于 Math 114 / EE229B 的内容。

与其他讲次的关联

• 讲次 7（Polynomials）：本讲的两个”发动机”——Property 1（次数 $d$ 的非零多项式至多 $d$ 个根）与 Property 2（$d+1$ 个点唯一确定次数 $\le d$ 的多项式）——直接来自 L07。定理 8.1 是 Property 2 的推论；定理 8.3、8.4、8.5 全部依赖 Property 1。L07 的系数表示 / 值表示对偶也正是 RS 码的定义本身：系数表示 $\to$ 值表示是编码，值表示 $\to$ 系数表示是译码。另外 L07 已给出 Shamir 方案的雏形，本讲把它补上了严格的安全性证明。
• 讲次 4（Modular Arithmetic）：整个方案在 $\mathbb{Z}_q$ 上做加法与乘法，份额与恢复值都是同余类；”所有算术 mod $q$”这句话就是 L04 的语言。
• 讲次 5（Euclid, FLT, CRT）：Lagrange 插值公式里的每个分母 $i_j-i_\ell$ 都要求逆元，其存在性来自 L05 的”$q$ 素数 $\Rightarrow$ 每个非零元可逆”；实际计算逆元用扩展欧几里得。$\Delta_j(x)$ 的构造（分子乘上”除自己以外所有 $(x-x_\ell)$”）与中国剩余定理中”单位分解”的构造思路完全同构——L07 的 Note 明确点出了这一类比。
• 讲次 6（RSA）：对照学习最有价值：RSA 用”单向函数 + 计算困难性”保护不可读性，纠错码用”高最小距离 + 冗余”保护可恢复性。两者都建立在模运算与有限域之上，但安全性假设的类型完全不同。
• 讲次 9、10（Graphs / Graphs II）：官方 Note 开篇即指出纠错码有两大流派——代数码（基于有限域上的多项式，本讲主题）与组合码（基于图论）。L09–L10 的图论正是组合码的语言；L10 将讨论的超立方体 (hypercube) 与一般图会在”低密度奇偶校验码 (LDPC)”等构造中再次出场。
• 讲次 11（Stable Matching）：与本讲同为”算法 + 正确性证明”的范式：Gale–Shapley 要证”算法终止”与”输出稳定”，本讲要证”插值唯一”与”译码正确”。两者都示范了”先设计能跑的算法，再用数学证明它给出的答案是唯一正确的”这一 CS70 核心方法论。
• 讲次 13（Computability）与算法复杂度：Berlekamp–Welch 的最大卖点是把”枚举 $\binom{n}{e}$ 个错误位置”这一指数时间搜索替换为一次多项式时间的线性方程组求解。这是”同一问题的不同表述导致截然不同复杂度”的标准案例。若允许 $e$ 超过 $\lfloor (d-1)/2\rfloor$，一般的最小距离译码问题是 NP 难的——这属于 L13 讨论的”困难/不可行”图景。
• 讲次 14（Counting）与讲次 19（Random Variables）：安全性论证里要数”有多少条候选曲线”，答案是 $q$ 条（L14 的乘法原理：$k$ 个系数各 $q$ 种取值，被 $k-1$ 个点约束后还剩 $q$ 种）；若把 $s$ 视为均匀随机变量，则份额 $(Y_1,\dots,Y_{k-1})$ 与 $s$ 独立，这正是 L19 的独立性语言。
• 讲次 17、18（Conditional Probability & Bayes / Independence）：定理 8.2 的结论可以精确表述为”$s$ 与任意 $k-1$ 个份额相互独立“（L18 的主题）；用 L17 的贝叶斯公式会说”后验 $=$ 先验”。这是”零泄露”最严格的说法。

关键要点

1. 一句话抓住 Shamir：秘密是曲线在 $x=0$ 处的截距，份额是曲线在其他点上的取值。$k$ 个点钉死曲线 $\to$ 截距暴露；$k-1$ 个点收敛不住曲线 $\to$ 截距可自由滑动 $q$ 个位置。
2. 正确性靠 Property 2，安全性靠”兼容性对称”。证明安全性时不能只说”算不出来”，必须对每一个猜测值 $s^{\prime}$ 构造一条过 $(0,s^{\prime})$ 与已知 $k-1$ 点的曲线，从而证明候选集合大小恒为 $q$（没有变小），信息量为 $0$ 比特。
3. 距离是编码的通用”货币”：$d$ 个距离单位可换 $d-1$ 个检错、$\lfloor (d-1)/2\rfloor$ 个纠错、$d-1$ 个纠擦除。因此纠错比擦除贵一倍：擦除只要 $n\ge k+e$，纠错要 $n\ge k+2e$。
4. Reed–Solomon 是 MDS 码：$d_{\min}=n-k+1$，在 $n,k$ 固定时达到 Singleton 上界。下界只用到”两条次数 $<k$ 的曲线至多相等 $k-1$ 次”；上界靠 $P(x)=\prod_{j=1}^{k-1}(x-\alpha_j)$ 与零多项式这一对显式构造。
5. Berlekamp–Welch 的核心恒等式：$Q(i)=r_iE(i)$ 对出错与不出错的位置同时成立。这一个恒等式把 $n$ 条方程、$k+2e$ 个未知数（$Q$ 的 $k+e$ 个系数 $+$ $E$ 的 $e$ 个系数）摆上台面。因为 $t<e$ 时 $E$ 可任意补因子，解 $(Q^{\prime},E^{\prime})$ 可以不唯一，但商 $Q^{\prime}/E^{\prime}$ 永远唯一（定理 8.5）。

常见误区与注意事项

1. 把”$k-1$ 人无信息”误解成”计算上算不出来”。这是信息论层面的结论：对 $k-1$ 人而言秘密的后验分布仍然均匀，与先验一模一样，就算给他们无限算力也得不到任何东西。反过来，若只实现了”计算上困难”（例如用哈希保护秘密），那就不满足本讲的门限定义，也不是 Shamir 方案。
2. 忘记”$q$ 必须是素数”（更一般地，必须是域的阶）。若在 $\mathbb{Z}8$ 这样的合数环上做插值，Property 1 直接失效：$x^3\equiv 0 \pmod 8$ 有 $x=0,2,4,6$ 四个根，一个三次多项式竟然有 4 个根，唯一性论证全面崩塌（详见讲次 7 的 Note 脚注）。同理，Lagrange 公式中的除法要求分母可逆，而 $\mathbb{Z}_m$ 中 $m$ 为合数时并非所有非零元都可逆。特别注意 $GF(2^{32})$ 与 $\mathbb{Z}{2^{32}}$ 不是一回事。
3. 混淆”擦除”与”错误”的冗余代价。擦除知道位置，$k$ 个擦除只需 $k$ 个额外符号；错误不知道位置，$k$ 个错误需要 $2k$ 个额外符号。若把两者混为一谈，就会设计出看似”够用”、实则无法唯一译码的方案——定理 8.3 与两个反例都说明了这一点。
4. 把”最小距离”算成”平均距离”或”最大距离”。$d_{\min}$ 是最坏那对码字的距离，它决定了保证能纠多少错；某对码字距离很大毫无用处。反过来，也不能因为”大多数码字对离得很远”就宣称纠错能力强。
5. 在 Berlekamp–Welch 里误以为 $(Q,E)$ 一定唯一，于是看到”无错”情形下解出一整族解就以为算法错了。正确理解是：无错时真实的 $E$ 完全不确定（没有错误位置需要标记），补的额外根可以任取，所以 $(Q^{\prime},E^{\prime})$ 有一族；但任何一组解的商都等于 $P$（定理 8.5 第 10–11 步）。算法的输出是 $P$，不是 $E$。
6. 忘记 $E(x)$ 的首一约定。本讲取 $E$ 为首一多项式，即把 $x^e$ 的系数固定为 1 而不作为未知数，这样未知数才恰好是 $e$ 个（$b_0,\dots,b_{e-1}$），总数才是 $k+2e$。若把 $x^e$ 的系数也当未知数，未知数就会比不等式所允许的多 1，论证会显得”解不出来”。
7. 误用”次数恰好 $k-1$”与”次数至多 $k-1$”。Shamir 方案要求曲线次数恰好 $k-1$（最高次系数非零），否则实际门限会降到 $k-1$；而 Reed–Solomon 的译码只关心”次数 $\le k-1$”，因为消息的最高系数可以恰好为 0。这两个约定必须在同一篇推导中保持一致。
8. 纠错与检错不能同时达到上界。定理 8.3 说 $d$ 能纠 $\lfloor(d-1)/2\rfloor$ 个错，也能检 $d-1$ 个错，但不能同时要求”纠 $t$ 个错并且检 $t+1$ 个错”之外的更强保证；经典结论是 $(d\ge 2t+s+1)$ 才能同时纠 $t$ 个错并检 $s$ 个错。混用两个界会得出过强的结论。

思考题（带答案）

Q1.（纯计算） 在 $GF(11)$ 上取 $k=3$、$s=5$，多项式 $P(x)=5+2x+3x^2$。份额为 $P(1),\dots,P(5)$。 (a) 算出 5 个份额。 (b) 用份额 2、3、4 通过 Lagrange 插值在 $x=0$ 处求值，恢复 $s$（写出每个基函数在 0 处的值）。 (c) 若只有份额 2、4 两份，攻击者能否排除 $s^{\prime}=0$ 这个猜测？请给出具体的相容曲线。

Q2.（概念/证明） 有人提出一个”简化版”方案：选一条次数为 $k-1$ 但常数项强制为 0 的随机曲线 $P$（即 $P(0)=0$），再把秘密 $s$ 作为整条曲线的公共平移量，即实际份额为 $\tilde P(x)=P(x)+s$ 在第 $i$ 点的值。请指出这个方案在门限方案的两条性质中的哪一条上失败，并给出具体的攻击。

Q3.（计算 + 概念） 在 $GF(7)$ 上，消息长度 $k=3$（$P$ 次数 $\le 2$），码字长度 $n=5$，求值点为 $1,2,3,4,5$。真实多项式 $P(x)=x^2+x+1$，码字为 $(3,0,6,0,3)$。设第 1 个坐标被篡改为 2，接收串 $r=(2,0,6,0,3)$。 (a) 写出 Berlekamp–Welch 的 5 个方程并解出 $Q,E$。 (b) 做长除法得 $P$，并说明错误位置。 (c) 若实际上没有任何错误（$r=(3,0,6,0,3)$），方程组会给出多少解？请说明为什么这不影响译码。

图 8.1  Shamir 秘密共享（GF(11)，n=5，k=3，s=5，P(x)=5+2x+3x^2）
================================================================
   份额分布（x 为参与方编号，y 为份额值）

   y
  10 |  o(1,10)  o(2,10)
   9 |
   8 |
   7 |
   6 |                      o(4,6)
   5 |     s(0,5)                o(3,5)
   4 |
   3 |
   2 |                              o(5,2)
   1 |
   0 +----+----+----+----+----+----+----> x
      0    1    2    3    4    5
      ^
      秘密 s = P(0) = 5   （这条曲线的"截距"就是秘密）

  任意 3 个 o  -> 曲线被钉死 -> 读出截距 5      （定理 8.1）
  任意 2 个 o  -> 曲线仍可自由摆动             （定理 8.2）
                  截距可以是 0..10 中任何一个：
                  s'=0  -> P'(x)=0+5x+5x^2
                  s'=5  -> P'(x)=5+2x+3x^2   <-- 真身
                  s'=7  -> P'(x)=7+3x
                  ...  共 11 条，全部相容
================================================================

图 8.2  擦除 vs 错误：为什么纠错要付双倍冗余
=============================================================
【擦除 erasure】接收方知道"洞"在哪，只需补上洞的个数
  发送  c1 c2 c3 c4 c5 c6
  接收  c1 -- c3 c4 c5 --      知道位置 2 和 6 丢了
        ^^ 洞有编号，等价于已知 x=2, x=6 而不知 y
  代价：k 个擦除  ->  多发 k 个符号   (码长 >= 消息长 + k)
        要求 d >= k+1                （定理 8.3(c)）

【错误 error】接收方收到同样多的符号，但不知哪几个是假的
  发送  c1 c2 c3 c4 c5 c6
  接收  r1 r2 r3 r4 r5 r6      其中至多 k 个 r_i != c_i，位置未知
        ?  ?  ?  ?  ?  ?        每个位置都可能是"洞"或"真值"
  代价：k 个错误  ->  多发 2k 个符号  (码长 >= 消息长 + 2k)
        要求 d >= 2k+1               （定理 8.3(a) 与 8.4）

  直觉：一个错误有两种解释（值被改了 / 位置算错了），
        纠错必须在"两个都可能是真码字"的情形之间做出唯一裁决，
        这就要求码字之间的距离比擦除情形再宽一倍。
=============================================================

图 8.3  汉明球：最小距离 d 如何决定纠错能力
=================================================================
码字空间（每颗 * 是一个码字；相邻两 * 的最短距离 d = 5，本例 t=2）

      ( . . . . . )                ( . . . . . )
     (  半径 t=2   )              (  半径 t=2   )
      (   的球     )              (   的球     )
       (          )                (          )
        *   o o                     *   o o
       o  *  o                      o  *  o
        o o                          o o
          \                          /
           \   球心距离 d >= 2t+1    /
            \                        /
             +---- 若两球相交 --------+
              则球心距离 <= 2t = 4 < d = 5  ==>  矛盾！
              所以半径 t = floor((d-1)/2) 的球两两不交
              接收串落在哪个球里 -> 判给该球心（唯一译码）

  d = 5:  t = 2  (纠 2 个错；检 4 个错；抗 4 个擦除)
  d = 4:  t = 1  (纠 1 个错；检 3 个错)
  d = 2:  t = 0  (一个错都纠不了，只能检出 1 个错)
  d = 1:  毫无防护（消息集合本身就处于这个状态）
=================================================================

图 8.4  Reed-Solomon 译码 = 用点重拟合曲线（GF(7), k=3, n=5, e=1）
=================================================================
  y
  6 |                 x  <- 真码字 P(3)=6
  5 |
  4 |
  3 |  * (1,3) <-- 真值           x(5,3)
  2 |  X  <-- 被篡改为 2
  1 |
  0 |        x(2,0)    x(4,0)
    +----+----+----+----+----> i
      1    2    3    4    5

  Berlekamp-Welch 两步走：
  (1) 解线性方程组 Q(i) = r_i * E(i)（i=1..5，5 个方程 5 个未知数）
        -> Q(x) = x^3 + 6 ,  E(x) = x + 6 = x - 1
        E 的根 x = 1  ==>  错误位置 e_1 = 1
  (2) 长除法 P = Q / E = (x^3+6)/(x-1) = x^2 + x + 1
        -> P(1) = 3 覆盖掉 X(1,2)，还原原始消息 (3,0,6)
=================================================================

图 8.5  为什么 n < k+2e 会失败（GF(7), k=3, e=1, n=4 反例）
=================================================================
 两条消息的码字（求值点 1,2,3,4）：

   P0 = 0           码字 c0 = (0, 0, 0, 0)
   P1 = x^2+4x+2    码字 c1 = (0, 0, 2, 6)
                        ^^^^^^^^^^^^
                    距离 d(c0,c1) = 2  =  n-k+1 = 4-3+1

 接收串 r = (0, 0, 2, 0)

   d(r, c0) = 1   <=  e = 1     --> 译码为 P0，秘密 = P0(0) = 0
   d(r, c1) = 1   <=  e = 1     --> 译码为 P1，秘密 = P1(0) = 2

  两个码字都在半径 1 的球内！译码结果不唯一，秘密无法确定。
  ==> 冗余必须加倍：n >= k + 2e  （本反例 n = k+2e-1 = 4）
=================================================================

附加算例（对照官方 Note 的擦除例子，$GF(7)$，$n=4$，$k=2$）：消息 $m_1=3,m_2=1,m_3=5,m_4=0$，唯一的三次多项式为 $P(x)=x^3+4x^2+5$。校验：$P(1)=1+4+5=10\equiv 3$，$P(2)=8+16+5=29\equiv 1$，$P(3)=27+36+5=68\equiv 5$（$68-63=5$），$P(4)=64+64+5=133\equiv 0$（$133-133=0$）✓。多发 2 个冗余字符：$P(5)=125+100+5=230\equiv 6$（$230-224=6$），$P(6)=216+144+5=365\equiv 1$（$365-364=1$）。码字为 $(3,1,5,0,6,1)$。若第 2、6 个包被丢弃，接收方拿到点 $(1,3),(3,5),(4,0),(5,6)$，四个点足以（$n=4$）重建 $P$；脚本用 Lagrange 基函数验证重建出的系数恰为 $(5,0,4,1)$，即 $P(x)=x^3+4x^2+5$ ✓。这同时演示了定理 8.3(c)：$d_{\min}=6-4+1=3$，可抗 $d-1=2$ 个擦除，恰好覆盖本例的 2 个丢失。

附加算例（Berlekamp–Welch 的另一个参数组合，$GF(7)$，消息长 4、$e=1$、码长 6）：用上面同一个 $P(x)=x^3+4x^2+5$，码字 $(3,1,5,0,6,1)$，设第 1 个字符被从 3 篡改为 2，接收串 $r=(2,1,5,0,6,1)$。此时 $Q$ 的次数 $\le k+e-1=4$，共 5 个系数，加上 $b_0$ 共 6 个未知数、6 条方程（方阵）。脚本解出 \(Q(x)=2+5x+3x^2+3x^3+x^4,\qquad E(x)=x+6=x-1 .\) 逐点校验 $Q(i)=r_iE(i)$：$i=1$ 时 $Q(1)=2+5+3+3+1=14\equiv 0$，$r_1E(1)=2\times 0=0$ ✓；$i=2$ 时 $Q(2)=2+10+12+24+16=64\equiv 1$，$r_2E(2)=1\times 1=1$ ✓；$i=5$ 时 $Q(5)=2+25+75+375+625=1102$，$1102\bmod 7=3$（$7\times157=1099$），$r_5E(5)=6\times 4=24\equiv 3$ ✓。长除法 \(\frac{Q(x)}{E(x)}=\frac{x^4+3x^3+3x^2+5x+2}{x-1}=x^3+4x^2+0x+5 ,\) 余式为零 ✓，恢复出 $P(x)=x^3+4x^2+5$，与原多项式一致；错误位置 $e_1=1$。 —