如何分摊秘密（七）

作者：安迁

十、拉格朗日插值法

本节介绍拉格朗日插值法，学过的读者请略过。

从数值分析的角度来看，拉格朗日插值法常被描述成是用多项式函数来逼近某个实际函数的方法，总有点“误差”的味道在里面。但从代数的角度来看，我们并不需要假设有额外的“实际函数”存在。我们可以更简单地说，拉格朗日插值法，就是通过若干个点上多项式函数的值来找出这个多项式本身的方法。

具体地说，假如f(x)是一个多项式，而且我们知道当x取值为a₁，a₂，……，a_n时，多项式的值分别是f(a₁)=b₁，f(a₂)=b₂，……，f(a_n)=b_n，我们希望能找到这个f(x)，也就是用诸a_i和b_i的值把多项式f(x)来表达出来。现在暂时假设a_i和b_i都是整数。当然，每个a_i必须各不相同。否则的话如果有a_i和a_j是一样的，b_i和b_j是不是一样？要是不一样，这相当于说f(x)在同一个点取两个不同的值，矛盾了；要是一样，相当于说同一个信息说了两遍，没必要。

给定一组a_i和b_i的值，可以求得的f(x)并不是唯一的。因为多项式p(x)=(x-a₁)(x-a₂)……(x-a_n)在每一个a_i处的值都是0，所以如果f(x)是一个满足上面要求的多项式，f(x)+p(x)q(x)也同样满足要求，其中q(x)可以是任何多项式。但是如果我们再加一个条件：规定f(x)的次数必须小于n，那么这个时候这样的f(x)就是唯一的了。因为如果有两个多项式f(x)和g(x)都满足要求而且次数都小于n，那么f(x)-g(x)就是一个在所有a_i处的值都是0，而且次数小于n的多项式，而我们知道这样的多项式只能是0，否则它就有n个不同的根却次数小于n，和代数基本定理矛盾（n-1次多项式最多只能有n-1个根）。所以从现在开始我们要求所找的f(x)的次数是小于n的。

找到f(x)的方法其实并不复杂。

先不管那些b_i，我们先找一个次数小于n的多项式r₁(x)，使得r₁(a₁)=1，r₁(a₂)=0，r₁(a₃)=0，……，r₁(a_n)=0，也即除了在a₁那点取值为1外，在其他a_i处取值都是0。

怎么找到r₁(x)？考虑下面的式子： (a₁-a₂)(a₁-a₃)……(a₁-a_n) 它的结果是一个不为0的数，因为a_i之间两两不同，设这个数是d。如果我们把上面式子中的a₁换成多项式的变量x，那么我们得到了一个n-1次多项式 (x-a₂)(x-a₃)……(x-a_n) 这个多项式在a₁处的取值当然就是上面的式子的值d，而在其他a_i处的值是0，因为这些乘积中总有一项是(a_i-a_i)=0。把上面的多项式除以d： (x-a₂)(x-a₃)……(x-a_n)/d 它在a₁处的取值是1，而在其他a_i处的值是0，就是我们需要的 r₁(x) = (x-a₂)(x-a₃)……(x-a_n)/((a₁-a₂)(a₁-a₃)……(a₁-a_n))

同样道理我们也可以找出在a₂那点取值为1外，在其他a_i处取值都是0的次数为n-1的多项式 r₂(x) = (x-a₁)(x-a₃)……(x-a_n)/((a₂-a₁)(a₂-a₃)……(a₂-a_n)) 以及类似的r₃(x)，……，r_n(x)。每个r_k(x)都在a_k那点取值为1，而在其余a_i处取值为0。

注意到上面这些r₂(x)只和a_i们有关，和b_i们无关。我们回过头来再考虑那些b_i，我们所求的f(x)不就是 f(x) = b₁r₁(x)+b₂r₂(x)+……+b_nr_n(x) 只要验证一下它在每个a_i的值可知所言不虚。这就是所谓的拉格朗日插值法。下面看看具体例子。

我们考虑6个点，也就是n=6，取a_i=i，其中i从1到6。这意味着我们将通过f(1)，f(2)，……，f(6)的值来找到f(x)。计算一下各r_i(x)： r₁(x) = (x-2)(x-3)(x-4)(x-5)(x-6)/((1-2)(1-3)(1-4)(1-5)(1-6)) = -(x-2)(x-3)(x-4)(x-5)(x-6)/120 r₂(x) = (x-1)(x-3)(x-4)(x-5)(x-6)/((2-1)(2-3)(2-4)(2-5)(2-6)) = (x-1)(x-3)(x-4)(x-5)(x-6)/24 r₃(x) = (x-1)(x-2)(x-4)(x-5)(x-6)/((3-1)(3-2)(3-4)(3-5)(3-6)) = -(x-1)(x-2)(x-4)(x-5)(x-6)/12 r₄(x) = (x-1)(x-2)(x-3)(x-5)(x-6)/((4-1)(4-2)(4-3)(4-5)(4-6)) = (x-1)(x-2)(x-3)(x-5)(x-6)/12 r₅(x) = (x-1)(x-2)(x-3)(x-4)(x-6)/((5-1)(5-2)(5-3)(5-4)(5-6)) = -(x-1)(x-2)(x-3)(x-4)(x-6)/24 r₆(x) = (x-1)(x-2)(x-3)(x-4)(x-5)/((6-1)(6-2)(6-3)(6-4)(6-5)) = (x-1)(x-2)(x-3)(x-4)(x-5)/120 值得注意的是，即便象最初所说，诸a_i和b_i都是整数，所得的多项式的系数也有可能不是整数，而是有理数。

如果b₁到b₆分别取1，4，9，16，25，36，那么 f(x) = r₁(x)+4r₂(x)+9r₃(x)+16r₄(x)+25r₅(x)+36r₆(x) = x² 这正是平方序列的通项公式。

如果b₁到b₆分别取1，1，2，3，5，8，那么 f(x) = r₁(x)+r₂(x)+2r₃(x)+3r₄(x)+5r₅(x)+8r₆(x) = -(1/40)x⁵+(11/24)x⁴-(25/8)x³+(241/24)x²-(287/20)x+8 这当然不是斐波那契数列的通项公式，只是以上式为通项公式的数列的前6项恰好和斐波那契数列相同，它再接下去的几项是8，-6，-55，-173……就和斐波那契数列完全不一样了。

如果取“边看边说序列”的前几项，把它们当作是十进制数，也就是b₁到b₆分别取1，11，21，1211，111221，312211，那么拉格朗日插值法照样能找到合适的多项式： f(x) = r₁(x)+11r₂(x)+21r₃(x)+1211r₄(x)+111221r₅(x)+312211r₆(x) = -(11597/6)x⁵+(100285/3)x⁴-(416905/2)x³+(1766885/3)x²-(2247644/3)x+337211 以上式为通项公式的数列的前几项是：1，11，21，1211，111221，312211，228921，-1103269，-5470279，-15711269……

中学数学课程里为什么不正式地介绍一下拉格朗日插值法呢？从难度上来说这并不高，结果也相当漂亮。我私底下以为，有部分原因会不会是一旦中学生掌握了这个找通项公式的大杀器，就会拿来和老师们抬杠——比如说，坚持认为1，1，2，3，5，8的下一项是8，或者干脆是任何一个数如12345678，因为反正用拉格朗日插值法也能产生出一个6次多项式，它的前7项分别是1，1，2，3，5，8，12345678。

在前面对拉格朗日插值法进行叙述时我们假设了a_i和b_i都是整数，我们发现最后得到的多项式的系数却未必是整数，但如果我们假设它们是有理数，那么最后得到的多项式的系数就一定是有理数，因为由构造过程可知，系数总是a_i和b_i之间的加减乘除。这个推理过程也可以应用到a_i和b_i都是实数或者复数的情况，最后所得的多项式系数也必定分别是实数的或是复数的，因为它们都是域。

很自然地，我们也可以考虑a_i和b_i取在有限域GF(N)上的情形，上面介绍拉格朗日插值法的所有论证都还成立——除了一点，GF(N)上没有代数基本定理。但是在GF(N)上照样有“n次多项式最多只有n个根”的结论（证明略），所以在GF(N)上关于拉格朗日插值法的叙述仍旧可以成立。

在下一节我们将看到，在有限域GF(N)上的拉格朗日插值，将成为有效率地分摊秘密的有力工具。