主题：如何分摊秘密（一）——从《鹿鼎记》中的四十二章经说起 -- 明日枯荷包

回到三个人分摊一个6位账户密码的问题来，如果说只要其中两个人同意就可以推出账户密码来，该怎么分摊秘密？

有个很简单的方法，还是按老规矩把账户密码拆成三个6位数，只有拿到所有这三个6位数才能推导出最终的密码。假设这三个数是A，B和C，老板让甲拿A和B，乙拿B和C，丙拿A和C。

很显然，任何单个人都无法通过自己手上的那两个数获得任何关于账号密码的知识，但是任何两个人在一起，总能凑齐ABC三个数字，从而得知账户密码。

这个办法也可以推广到一般的N个人只要有超过M个人同意（N>=M>0）就可以得知最终秘密的情况。想法就是把最终秘密拆成许多份，而每个人都拿其中的若干份，然后想办法保证让少于M个人在一起，一定凑不齐所有的份数，而如果M个人在一起则一定能凑足所有的份数。

不过我们也可以从另一个方面考虑，这个考虑方法解释起来比较简单。（其实也就是下面multiple的方法，可我觉得我说得比他详细，比他清楚）（8月23日注：我的方法和multiple兄的方法似乎不同，请看下面我和乌贼兄的讨论：乌贼:按有个疑问）

同一个6位数的账号密码可以用不同的随机数拆成不同的分摊方法。比如123456要拆成3份，可以是153607，582149，598710，也可以是405071，951239，877256，等等等等。如果要求在5个人中分摊秘密，使得任何其中3个人同意就可以知道秘密，可以这样做：

找到所有5个人中的“三人组合”，这个我们在中学排列组合课里学过，是5件东西取3件的组合取法，一共有(5,3)=5!/(3!(5-3)!)=10个“三人组合”。对于每个这样的三人组合，我们都把那个账号密码象前面那样用随机数拆成3份，然后给这个三人组合中每人一份。一共会拆出10x3=30个6位数来。每个人当然都会属于好几个三人组合。对一个具体的甲，他分别属于(4,2)=4!/(2!2!)=6个不同的“三人组合”，所以他会拿到6个6位数，其中每个6位数都是其中一个三人组合中分摊给他的那份秘密。5个人一共有5x6=30个6位数，这和上面的结果对上了。

甲拿到属于他的那6个数，会增加他对账号密码的知识吗？不会，其中单独的任何一个数都不会使他增加知识。而这6个数分别是6个分拆中的一部分，这6个分拆之间是独立没有关系的，于是就算拿了这6个数也没法组合起来得到对账号密码的新知识。

如果是两个人合谋，比如甲和乙，那么他们最多能够凑到诸如“甲乙丙”“甲乙丁”之类三人组合中那些分拆里3份中的2份，可这还是不够，因为一定要拿到一个分拆的所有3个部分，才能知道账户密码。

如果有任何三个人在一起，比如甲乙丙，那么他们就凑齐了他们那个三人组合的账户密码分拆的所有3个部分，于是就能知道账户密码。

这个方法很容易推广成一般的N个人中只要有超过M个人同意（N>=M>0）就可以得知最终秘密的情况。N个人中的M人组合有(N,M)=N!(M!(N-M)!)=A个，我们就把秘密对这A个组用A种方法拆分，每种方法都独立地将秘密拆成M份，然后给对应的这个M人组合中每人一份。就象上面的特殊的N=5，M=3的情况看到的，少于M个人在一起是没办法恢复出最终秘密的，但是只要有任何M个人在一起，就可以用为这个M人组合的拆分信息恢复出最终秘密。

于是我们就知道了，从理论上来说，无论N和M是多少，我们总能找到方法来让这N个人分摊秘密，使得少于M个人在一起无法知道最终秘密（不仅如此，是一点新知识都不增加），而M个人以上在一起就能够得知最终秘密。不过从实际上来说，这个方法只能用在N和M不大的情况，比如上面N=5，M=3的情况，每个人记6个6位数，也还好。但是N=100，M=80呢？组合爆炸了。其中的80人组合会有(100,80)=100!/(80!20!)=535983370403809682970个，超过5x10^20个。而每个人得记住(99,79)=99!/(79!20!)=428786696323047746376也就是超过4x10^20个6位数，这得拿多少硬盘才存得下来啊。还不说分拆啊检索啊所需要的时间。而且这还只是要分摊一个6位数，如果是一个大文件，那就更提也别提了。一句话，这种简单的想法不实用。

前面那种“所有人都同意秘密才可揭晓”的情况下，每个人要掌握的秘密的长度都和最终秘密的长度一样，要分摊一个6位数的密码，3个人分摊就会拆成3个6位数，100个人分摊就拆成100个6位数，每个人总是只要记住一个6位数就可以了。如果在“N个人M个同意”的情况下，不管是什么M和N，要求每个人记的数也都只是一个6位数（或者一般地，是和最终秘密一样大小的一个信息），那该有多好啊。

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

喘气喘气……

• 数学闲话（一）——代数结构(3) 同余