如何分摊秘密（六）

八、组合爆炸

如何用前一节中“准入集”的方法来解决m个人只要有至少k个人同意（m≥k>0）就可以得知最终秘密的问题？

很简单，这种情况下的准入集就是所有的“k人组合”。我们在中学数学中学过，在m个人中选k个人的方法是组合数(m,k) = m!/(k!(m-k)!)，其中!是阶乘运算。只需为(m,k)个“k人组合”中的每一组合独立地将秘密的分拆成k部分，并将各部分分摊给此组合中的k人，就得到了所求的分摊秘密的方法。

举个具体例子，如果要求在5个人中分摊秘密，使得其中任何3个人同意就可以知道秘密，可以这样做：5个人中的“三人组合”一共有(5,3)=5!/(3!(5-3)!)=10个。对于每个这样的三人组合，我们都把秘密独立地拆成3份，然后给这个三人组合中每人一份。一共会拆出10x3=30份。每个人都会属于好几个三人组合。对一个具体的甲，他分别属于(4,2)=4!/(2!2!)=6个不同的“三人组合”，所以他会拿到6份分摊部分。5个人一共有5x6=30份，和上面的结果自洽。

到此为止，我们从理论上解决了本文前面提出的所有问题。

但从实际应用上来说，上面这个“为m人中的每个k人组合提供一个独立的分拆”的方法只适合m和k不大的情况。每个独立分拆都会把原秘密拆分成k份和原秘密同样大小的信息。比如在上面m=5，k=3的例子中，一共会分拆出30份和原秘密同样大小的部分来，每人保存其中的6份，不算太困难。

但是如果m=100，k=80呢？100人中的80人组合会有(100,80)=100!/(80!20!)=535983370403809682970个，每一个组合需要将秘密拆成80份，每个人需要保存的份数是(99,79)=99!/(79!20!)=428786696323047746376。哪怕那个秘密只有1比特，每个人需要保存的信息也达到了428786696323047746376比特，也即差不多51115357437497兆字节，需要大约5千万个1TB的硬盘才能存下。如果被分摊的秘密包含信息更多（比如藏宝图），那么分摊后所需保存的信息量也要相应增加。所以这种策略并不实用。

在前面那种“所有人都同意秘密才可揭晓”的情况下，分摊给每个人保存的拆分部分的大小和原始秘密的大小一样：要分摊一个6位数的密码，3个人分摊就会拆成3个6位数，100个人分摊就拆成100个6位数，每个人总是只要记住一个6位数就可以了。藏宝图大小约为412MB，八位旗主每人也只需保存一个412MB的文件。如果在“m个人至少k个同意便可揭晓秘密”的情况下，不管是什么m和k，要求每个人保存的信息也都只和原始秘密一样大小，那该有多好啊。

好消息是，这种方法是有的；坏消息是，我们需要稍微高深一点的数学知识才能理解这个方法。

九、更多一点同余的知识

让我们继续第四节中关于同余类的讨论。和第四节一样，先假设已经固定了一个大于1的整数N。

我们已经看到，同余类之间可以象整数之间那样做加法和减法。实际上，同余类之间也一样可以做乘法。类似于加法，同余类的乘法也满足对任何整数a和b，[a]×[b]=[a×b]。如果用余数的语言表述出来，就是“两个整数的积除以N的余数，等于这两个整数分别除以N后的余数的积除以N的余数”，容易证明这是对的。

比如当N=12时，[3]×[7]=[21]=[9]，[4]×[3]=[12]=[0]。

上面第二个等式的意思是“除以12余数为4的整数和除以12余数为3的整数相乘，结果总能被12整除”，这并不令人吃惊；但从另一个角度看，这相当于说在同余类的世界里，有可能两个非零的元素相乘，也会得到零元素，这和整数的乘法不一样。这就造成了一个后果：在以12为模的同余类中是不能定义乘法的逆运算即除法的（当然我们不要求能定义除以零的运算，当我们说“能定义除法”时，我们指的是能够除以所有不为零的元素）。比如说，[1]/[3]会是什么？一方面，([1]/[3])×[3]×[4]=([1]/[3]×[3])×[4]=[1]×[4]=[4]，另一方面([1]/[3])×[3]×[4]=([1]/[3])×([3]×[4])=([1]/[3])×[0]=[0]。这和在整数中不能做除法1/3的原因是不一样的，因为虽然1/3不属于整数，但是可以通过把整数集合扩充为有理数集合的方法，使得这个除法可以进行。上面不能做除法[1]/[3]的原因更加彻底，是一个矛盾，无法通过扩充同余类集合来解决。也许能通过否定乘法的结合律，或是让零乘某数也可以不为零来解决矛盾，得到极为怪异的运算法则，但这很难算是乘法的逆运算。

如果我们稍微研究一下上面的例子，会发现在以12为模的同余类中不能定义除法的原因其实是因为12可以被分解成3×4。那么如果我们取N为不可被分解的素数，比如说N=7会怎么样？如同奇迹发生一般，这下不但我们可以定义除法，而且无需经过象整数扩充到有理数这样一个步骤——除法已经在那里了。

设N=7，考虑以7为模的同余类[0]，[1]，……，[6]。我们有 [1]×[1]=[1]， [2]×[4]=[8]=[1]， [3]×[5]=[15]=[1]， [6]×[6]=[36]=[1]。 于是被[1]除的结果就很显然了：[1]/[1]=[1]，[1]/[2]=[4]，[1]/[3]=[5]，[1]/[4]=[2]，[1]/[5]=[3]，[1]/[6]=[6]。除法的结果也显而易见了，因为[a]/[b]=[a]×([1]/[b])，比如[5]/[3]=[5]×[5]=[25]=[4]——本来我们就有[4]×[3]=[12]=[5]。

这是一个一般的结果，对于任何（正）素数N，以N为模的同余类之间都能做加减乘除——当然，不能除以零。我们在这里就不做严格证明了，只提示一点：当N是素数时，对任何整数t，用欧氏辗转相除法，我们都能找到两个整数u和v，使得uN+vt=1；于是在以N为模的同余类中，[uN+vt]=[1]，也即[v][t]=[1]，于是[1]/[t]=[v]。按照代数学的语言，以N为模的同余类构成了一个域。我们在中学里就碰见过一些域：有理数域，实数域和复数域，它们内部的元素间都能做加减乘除。但它们都拥有无限个元素，以N为模的同余类则构成了一个拥有有限个元素的域，是有限域，我们把它记作GF(N)，其中GF是Galois Field即伽罗华域的缩写，以纪念天才的法国数学家埃瓦里斯特·伽罗华。