# 多项式（Polynomials）

多项式对我们而言并不陌生，从中学的一次、二次函数到大学线性代数里的$n$次多项式，它在代数学里具有重要的作用。而在本节，我们将尝试将多项式应用于模运算及密码学的应用中，探讨如何应用其性质构造秘钥共享。

• 首先我们回顾一下多项式的形式：$p(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots+a_1x+a_0$，其中$x$为变量，$a_i(0\leq i\leq d)$为系数（均为实数），$d$为多项式的次数（degree）。
• 定义多项式$p(x)$的根$a$满足：$p(a)=0$（即函数图像与$x$轴的交点坐标）
• 下面给出两个关于多项式的重要性质：
  1. 任意$d$次非零多项式至多有$d$个根。
  2. 给定$d+1$个点$(x_1,y_1),\cdots,(x_{d+1},y_{d+1})$，其中所有点的$x$坐标互不相同，那么就有且仅有一个$d$次多项式$p(x)$满足$p(x_i)=y_i(1\leq i\leq d+1)$。

# 多项式插值（Polynomial Interpolation）

• 那么，如何从已知的$d+1$个点推出$d$次多项式的表达式呢？这里就要用到一种插值的方法：拉格朗日插值。
• 它的原理本质与中国剩余定理比较相似：即构造一系列项的和，对于每个项，当代入某个点$x_i$时值为$y_i$，而代入$x_j(j\neq i)$时值为$0$。
• 具体而言，我们可以构造以下基项：

  $$\Delta_i(x)=\frac{\prod_{j\neq i}(x-x_j)}{\prod_{j\neq i}(x_i-x_j)}=\left\{ \begin{aligned} &1,x=x_i\\ &0,x\neq x_i \end{aligned} \right.$$

  那么多项式$p(x)$就可以表示为：

  $$p(x)=\sum_{i=1}^{d+1}y_i\Delta_i(x)$$

• 举个简单的例子：假设多项式函数过点$(1,5),(6,8),(7,2)$，那么各个$\Delta_i(x)$可如下计算：

  $$\begin{aligned} &\Delta_1(x)=\frac{(x-6)(x-7)}{(1-6)(1-7)}=\frac{1}{30}x^{2} - \frac{13}{30}x + \frac{7}{5}\\ &\Delta_2(x)=\frac{(x-1)(x-7)}{(6-1)(6-7)}=-\frac{1}{5}x^{2} + \frac{8}{5}x - \frac{7}{5}\\ &\Delta_3(x)=\frac{(x-1)(x-6)}{(7-1)(7-6)}=\frac{1}{6}x^{2} - \frac{7}{6}x + 1 \end{aligned}$$

• 所以多项式为

  $$p(x)=5\Delta_1(x)+8\Delta_2(x)+2\Delta_3(x)=-\frac{11}{10}x^{2}+\frac{83}{10}x-\frac{11}{5}$$

• 可以验证其满足经过这三个点。

# 性质2的证明

• 前面我们已经证明了存在性，下面就来证明其唯一性。
• 假设除了$p(x)$，还有另一个不同的多项式$q(x)$满足经过这$d+1$个点。则考察$r(x)=p(x)-q(x)$：因为$p(x)$与$q(x)$均为$d$次多项式，所以$r(x)$的次数也至多为$d$，那么由性质1（后面会证明），$r(x)$至多有$d$个根。而又因为$p(x)-q(x)=0$在$d+1$个点上均成立，故$r(x)$应该有$d+1$个根，产生矛盾。所以只能$p(x)=q(x)$。

# 多项式除法（Polynomial Division）

• 在对性质1进行证明之前，先简要说明下多项式除法。
• 多项式除法类似带余除法，形式如下：

  $$p(x)=q'(x)q(x)+r(x)$$

  其中$p(x)$为被除式，$q(x)$为除式，$q'(x)$为商式，$r(x)$为余式（且次数低于$q(x)$）。
• 而具体的计算可以使用长除法（在此省略）。

# 性质1的证明

• 为了证明性质1，我们先证明下面两个引理：
  1. 如果$a$是$d$次多项式$p(x)$的根（$d\geq 1$），那么$p(x)$可表示为$(x-a)q(x)$，其中$q(x)$为$d-1$次多项式。
  • 由条件得$(x-a)\mid p(x)$，故$p(x)=(x-a)q(x)+r(x)$，而$r(x)$次数只能为$0$，所以只能为常数项$c$。又因为$p(a)=0$，所以$c=0$，故原式成立。
  2. 如果$d$次多项式$p(x)$有$d$个各不相同的根$a_1,\cdots,a_d$，那么它就可以表示为$c(x-a_1)\cdots(x-a_d)$，其中$c$为非零实数。
  • 对$d$进行归纳：
    • 当$d=0$时，结论显然成立；
    • 若$d=k$时结论成立，那么对于$d=k+1$次多项式$p(x)$（根为$a_1,\cdots,a_{k+1}$），由上面的引理得$p(x)=(x-a_{k+1})q(x)$，其中$q(x)$为$k$次多项式。
    • 又因为$p(a_i)=(a_i-a_{k+1})q(a_i)=0$对任意$1\leq i\leq k$均成立，故$a_1,\cdots,a_k$均为$q(x)$的根。由归纳假设得$q(x)=c(x-a_1)\cdots(x-a_k)$（$c$为非零实数），所以$p(x)=c(x-a_1)\cdots(x-a_k)(x-a_{k+1})$。
    • 归纳完成。
• 有了第二条引理，我们就能立刻得到性质1（因为任意$a\notin\{a_1,\cdots,a_{d}\}$都不是$p(x)$的根）。

# 有限域（Finite Fields）

• 下面我们对多项式系数的数域进行讨论。上面的所有结论对应的系数都是在实数域上，但当我们将实数域换成复数域或有理数域时，这些结论也成立。然而，如果换成整数域（或自然数域），结论就不一定成立（具体而言，性质2不成立）。
• 实际上，我们对两个性质进行的证明都是基于其对应数域的运算封闭性展开的，所以对于整数域（自然数域），因为其在除法计算上不封闭，所以性质2就无法推出。
• 不过，对于整系数多项式，我们可以加入模$p$运算（这里$p$为质数），将整数域限制在$\{0,1,\cdots,p-1\}$，这样就又能做到四则运算均封闭了（做除法时除了$0$都存在乘法逆元）。所以在这个数域上，两条性质同样成立。
  • 注：如果$p$为合数又会导致两个性质不成立。比如：当$p=4$时，$x^3\equiv 0(\mathrm{mod}\hspace{0.2em}4)$的解有$0,2,4,6$，不满足性质1，类似也不满足性质2。
  • 对于这个有限域，也被记为$F_p$或$GF_p$（$G$代表Galois，伽罗瓦）【这就涉及到一些群论（抽象代数）的一些知识，感兴趣的可自行探索】

# 多项式个数统计

• 对于模$p$的整数域上的多项式，我们可以进一步研究以下问题：经过若干个点的不同$d$次多项式有多少？如果要从系数角度讨论满足的多项式会比较复杂，但如果我们换个角度——从多项式经过的点的角度，那么就会简单很多：
  • 由上面得到的结论，一个$d$次多项式至少需要$d+1$个不同点唯一确定。那么，如果给定了$m$个点（$m\leq d+1$），就剩下$d+1-m$个点没有被确定，而每个点的值域均为$\{0,1,\cdots,p-1\}$种可能，总共就有$p^{d+1-m}$种可能的多项式。

# 秘密共享（Secret Sharing）

• 那么多项式如何应用在秘密共享系统中呢？我们可以想象下面这个场景：
  • 为了预防敌国的打击，C国部署了核弹防御系统，为了保证非必要不启用，系统设置了核弹发射密码（这里简化为整数$s$）；而密码只能由$n$个重要人员得到，且：
    • 只有这些人中至少$k(k>1)$个人共享信息，密码才能被计算出；
    • 任意$k-1$个人共享信息，都无法计算出真实密码；
• 这里就可以使用多项式为各个人员分配信息：
  • 首先，确定一个比$s$大的质数$p$，将数域限制在模$p$的整数域中；
  • 然后，随机生成一个$k-1$次多项式$P(x)$，要求满足$P(0)=s$；接着分别将$P(1),P(2),\cdots,P(n)$的值提供给各个重要人员。
• 那么：
  • 对于其中任意$k-1$个重要人员，如果他们共享信息，那么就只能确定多项式经过的$k-1$个点，而满足条件的多项式仍然有$k$个，即密码仍然有$k$种可能（这样猜测正确的概率与每个人单独猜测的概率相同）；
  • 而只要人员数达到$k$个，就可以利用拉格朗日插值法（注：涉及到的所有除法都转化为乘以对应的乘法逆）解出$P(x)$，进而计算出$s$。
• 所以这种系统就保证了共同决策的最小规模，维护了系统的安全。