如何分摊秘密（四）

四、一点同余的知识

在上节中我们用了几次诸如“如果小于0则加上1000000”“如果大于1000000则减去1000000”的操作，这样的说法在推广时就变得累赘。这些加减1000000操作的目的无非是希望最后的结果在0到999999之间，这其实就是求除以1000000后的余数的操作。我们需要更好的数学语言，也就是同余类。如果读者学过同余类，本节可以跳过不看。

首先我们必须象在前一节中那样，先固定一个大于1的整数N。上节中的1000000太大，用来说明问题不方便，本节中我们作例子时将取N=12。

任何一个整数除以N，都有一个介于0和N-1之间的余数。如果两个整数除以N的余数相同，我们就说这两个整数关于模N同余。比如当N=12时，64除以12的余数是4，-20除以12的余数也是4，64和-20关于模12同余。这就把所有整数分成了N类，每一类除以N的余数分别是0，1，……，N-1。

这N类整数有趣的地方是，如果我们把每类整数看作一个单独的东西（叫做关于模N的同余类），这N个东西之间可以做加法。比如说，“除以12余2”这类整数，可以加上“除以12余3”这类整数，得到结果“除以12余5”这类整数。如果我们用[n]来表示“（按照除以12的余数来分类），n所在的那一类”，那么我们就有[17]=[-7]，因为等式两边都是“除以12余5”这类整数。我们也有[-8]+[25]=[5]这样的结果，因为-8在的那一类就是“除以12余4”，而25在的那一类则是“除以12余1”，而这两类整数中分别随意挑一个整数相加，就会得到一个“除以12余5”的整数，属于5所在的那类数中。

同余类加法的计算相当方便，因为对任何整数a和b，[a]+[b]=[a+b]。注意到等式两边的那两个+号的意义是不一样的，左边那个+号是同余类之间的加法，右边那个是关于整数的加法。我们再举两个在模12下的同余类加法的例子：[100]+[1000]=[1100]=[91×12+8]=[8]，[8]+[4]=[0]。后面这个结果并不让人吃惊，因为[8]=[-4]。

同余类之间能作加法，也能作它的逆运算减法，规则和加法类似：[a]-[b]=[a-b]。大家可以试着举几个在模12下的同余类减法的例子。

要注意的一点是，在用[]符号时我们必须已经明确了N是什么。如果不说明是在模多少的情况下，光写[17]=[-7]是完全没有意义的；这个等式在模12下成立，在模10下就不成立——17除以10的余数是7，而-7除以10的余数是3，并不相同。

同余关系和同余类的概念相当简单，但是它在数学各领域中的重要地位是怎么强调也不过分的。它的有趣之处在上面这些例子里还没显示出来——在讨论它们之间的乘法（和除法）时我们会看到非同一般的现象，但那是后话，暂且不提。现代代数学入门的难点之一就是要从初等代数仅考虑常见的数（如整数、实数、复数等等）之间的运算的思考方式，切换到需要考虑一些比较复杂的数学对象（比如上面的同余类）之间的运算。这是学习代数学的一个坎，如果迈过去了，会对代数学进一步的学习有“领悟”的帮助；再回头一看，也许会连坎都看不到，搞不懂自己为什么原来会在这么简单的事情上搞不懂。但如果迈不过去，对代数学的学习就几乎不可能继续下去。

现在我们用同余类的语言来描述一下前面一节中两人之间分摊秘密的方法。首先我们固定一个大于1的整数N，需要分摊的秘密是0到N-1之间的一个数s。考虑以N为模的N个同余类[0]，[1]，……，[N-1]，可以把要分摊的秘密看作是同余类[s]。要在甲乙两人间分摊这个秘密，只需用能均匀地随机产生0到N-1之间的数字的随机产生器产生出一个数字a，把同余类[a]给甲，把同余类[s]-[a]给乙就行了。当甲和乙需要揭开秘密时，只要把各自拥有的两个同余类相加：[a]+[s]-[a]=[s]，就得到了秘密[s]。

这个说法的方便之处是，如果两个数相差N，那么它们必定是关于N同余的，它们所在的同余类是相同的。比如在N=1000000时，[-611593]和[388407]是同一个东西，而不像-611593和388407那样相差1000000，这样就不用说“如果小于0则加上1000000”之类的话了。

不过如果用现代数学语言来描述这事只有这么点好处，实在是费牛劲讲了一件在前一节能用很浅显的语言就讲明白的事情，有孔乙己的茴字四种写法之嫌。我们将在后面看到使用这种语言的进一步的好处甚至是必不可少之处，所以还请读者暂时先容忍一下。

五、更多人之间分摊秘密

如果需要在三个人或更多人之间分摊秘密怎么办？

仍旧是以那个6位数密码为例。假设现在老板要派三个人甲乙丙去。

老板随机产生两个0到999999之间的数，比如是953607和582149，把它们分别给甲和乙，然后用真正的密码123456减这两个数字得到-1412300，加上两个1000000使得结果处于0和999999之间，得到587700，把这个数字给丙。当甲乙丙需要揭开秘密时，只需将他们三人手中的三个数字相加：953607+582149+587700=2123456，然后减去两个1000000使得结果处于0和999999之间，得到123456。

对于一般的N并按同余类的语言来说，如果我们有秘密[s]要在甲乙丙三人间分摊，只要均匀地独立地随机产生两个0到N-1之间的整数a和b，将同余类[a]给甲，同余类[b]给乙，同余类[s]-[a]-[b]给丙。当甲乙丙需要揭开秘密时，只要把各自拥有的三个同余类相加：[a]+[b]+[s]-[a]-[b]=[s]，就得到了秘密[s]。

让我们来看看还未付款前，甲乙丙分别掌握和知道着怎样的秘密。很明显，甲乙丙分别掌握着953607、582149和587700，可他们知道什么秘密呢？

和两人分摊秘密时类似，甲乙手里的那两个数根本就是随便产生出来的，不可能增加对真正秘密的了解程度。丙靠他的数也一样不行，和两人分摊秘密时乙的情况差不多。

如果其中有两人合谋怎么办？比如甲和乙合谋——没用，他们那俩数都是随便产生出来的。乙和丙合谋？这就成了两人分摊秘密情况的变体，只是原先的乙如今是乙和丙的合体，靠乙和丙手中的数无法增加对甲手中的数的了解程度。甲和丙同谋的情况也一样。

注意到上面在描述产生随机数的过程时多了“独立地”这个条件。因为这次需要产生两个随机数，这两个随机数之间不能有某种联系。如果那个随机数产生器产生出953607后再产生随机数时会发生更容易产生出582149的情况，那么甲在拿到953607时，就会知道乙手中的随机数是582149的可能性要超过1/1000000。于是当甲和丙合谋时，就会知道账号密码是123456的可能性要超过1/1000000，也就是知道了更多的秘密。这里我们又一次看到（伪）随机数产生器质量的重要性。

把三人之间分摊秘密的方法推广到更多个人就很容易了。这里只用同余类的语言来叙述：对于固定的N，如果有秘密[s]要在m人之间分摊（其中m是大于或等于3的自然数），只要均匀地独立地随机产生m-1个0到N-1之间的整数a₁、a₂、……、a_m-1；对每个1到m-1间的自然数i，将同余类[a_i]给第i人，而将同余类[s]-[a₁]-[a₂]-……-[a_m-1]给第m人。当需要揭开秘密时，只要把所有人各自拥有的同余类相加就得到秘密[s]。对于其中任何m-1人以下合谋不能知道更多的秘密的分析也类似于三人的情况，不再赘述。