如何分摊秘密(六)

摘要

如何用前一节中“准入集”的方法来解决m个人只要有至少k个人同意(m≥k>0)就可以得知最终秘密的问题?很简单,这种情况下的准入集就是所有的“k人组合”。我们在中学数学中学过,在m个人中选k个人的方法是组合数(m,k) = m!/(k!(m-k)!),其中!是阶乘运算。只需为(m,k)个“k人组合”中的每一组合独立地将秘密的分拆成k部分,并将各部分分摊给此组合中的k人,就得到了所求的分摊秘密的方法。

调整大小 1八、组合爆炸

如何用前一节中“准入集”的方法来解决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/4的原因是不一样的,因为虽然1/4不属于整数,但是可以通过把整数集合扩充为有理数集合的方法,使得这个除法可以进行。上面不能做除法[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即伽罗华域的缩写,以纪念天才的法国数学家埃瓦里斯特·伽罗华。

(待续)

您还未添加分享代码,请到主题选项中,添加百度分享代码!

您可以选择一种方式赞助本站

安安以迁迁

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

图片 表情