五千年(敝帚自珍)

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

共:💬63 🌺987
全看分页树展 · 主题 跟帖
家园 按有个疑问

找到所有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位数,这和上面的结果对上了。

-----------------------------------------------------

这个方法很容易推广成一般的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人组合的拆分信息恢复出最终秘密。

这两段的说法和multiple兄的结果似乎有矛盾。如用(6,3)验算结果相差很多。multiple兄的结果和按想出来的一样。

我以为老兄5选3的解释(第一段)应当是5人当中4人可组合出秘密的情况。

而后面的应当是N人中任M+1人可组合出秘密的情况。

这样就和Multiple兄的结果吻合。

不知对否。


本帖一共被 1 帖 引用 (帖内工具实现)
全看分页树展 · 主题 跟帖


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河