![](http://image60.360doc.cn/DownloadImg/2013/05/0322/32076941_1.jpg)
信息世界给我们带来了很多便利,同时也没有给我们少添麻烦。物理世界中能轻松办到的事,在信息世界中却能让人伤透脑筋。让我们来考虑这样一个场景:两个人在电话中为一件小事争执不休,最后双方决定通过抛掷硬币来解决争端。在没有第三者的帮助下,通话双方有办法在电话里模拟抛掷一枚公平的硬币吗?
一些不太理想的方案
最容易想到的方案便是,A 先抛掷一枚硬币,然后在电话中把结果告诉 B。这种方案给了 A 很大的权力——A 完全可以选择谎报硬币抛掷结果,反正 B 也看不到真实的情况。如果通话双方彼此不信任的话,这种方案是不可行的。
另一种常用的方法就是两人在电话上玩语音版的“石头剪子布”——双方同时喊出“剪刀”、“石头”、“布”中的一个。可惜这种方案的公正性同样值得商讨:我们不能忽略两人玩心理游戏实力过于悬殊,或者一方可以不被察觉地延迟出招等不公平情况的出现。
下面这个方案则多少让人感觉更公正一些 :A 随便考 B 一道题,比方说“果壳网有多少个主题站”;如果 B 回答对了,就算 B 赢得这场争执,否则就算 A 获胜。这种方案似乎更靠谱,但难免还是漏洞百出。首先,公平性依然是老大难:B 有可能非常博学,没有什么答不上来的;或者 A 知道 B 的“弱点”,故意考 B 一道他不会的题目。其次,A 仍然有耍赖皮的空间—— A 可以出一道有多个答案的脑筋急转弯,比如说“树上七(骑)只猴,树下一只猴”,无论 B 回答什么,A 都可以判 B 答错。另外还有一种不太要命,但也不容忽视的隐患:出于某种目的,B 可以故意装作答不上来。也就是说,如果 B 知道题目的答案,B 就拥有了故意输掉的权力,这不符合抛掷硬币的精神——听天由命。
一个几乎完美的方案
不过,虽然漏洞多多,思路却值得借鉴。为了避免上述漏洞,A 提出的问题最好是二选一的问题,两个选项都有可能成为答案,概率各占 50%;回答它没有任何技巧,只能凭借猜测;而答案则必须是唯一的,并且很容易验证答案的正确性。细心想想,这样的问题倒也不少——比方说今天的某某报纸头条新闻中句号的个数是奇数还是偶数,或者圆周率前 51 位中小于 5 的数字多还是大于等于 5 的数字多。A 提出这样的问题后,要求 B 立即作答;面对这样的问题,B 没有任何答题技巧可言,只能瞎猜一个。之后两人便可花时间验证答案的正确性:如果 B 正好猜对了,视硬币抛掷结果为正,B 赢得这场争执;如果 B 猜测有误,则硬币抛掷结果为反,A 最终获胜。
这样的方案几乎是完美的了,我们只差一点了——这个方案不具有可重复性。之前出过的题目是不能重复使用的,一是为了避免 B 事先作弊,二也是考虑到通话双方所处环境得有验证答案的工具。因此,每次需要抛掷硬币时,A 都要想出一个全新的“公平问题”来。于是我们想到,能否构造出一套数学规则,让我们产生出无穷无尽的、纯数学形式的公平问题呢?
公平的电子抛币协议
在数学中,有一个非常典型的“正则易、逆则难”的问题:你很容易算出两个数的乘积是多少,却没法迅速找出一个大数等于哪两个数的乘积。
有些数能够表示成更小的数的乘积,比如 8 可以写成 2×4,35 可以写成 5×7。这样的数就被称为“合数”。另一些数则比较特殊,它不能写成更小的数的乘积,比如 7、23、67、191 等等,这样的数就叫做“素数”。素数拥有很多美妙的性质,它们不但让数学家们如痴如醉,在信息安全领域也有很多漂亮的应用。
选取两个素数,比方说 23 和 67,然后把它们乘在一起,能够得到一个新的数 1541。不过,除非一个数一个数地去试,否则你没办法判断出 1541 可以分成哪两个数之积。也就是说,对于“1541 能分成哪两个数的乘积”这个问题,回答起来相当困难,验证答案的正确性却很容易。
利用这个思路,我们能得到很多公平的电子抛币方案。比方说,先让 A 抛掷一枚硬币,如果正面朝上,就选择两个 1000 左右的素数;否则就选择三个 100 左右的素数。然后 A 把选出的素数乘起来,把结果告诉 B,让 B 猜猜看这个数是两个数的乘积还是三个数的乘积。要想获得正确答案,B 没有什么更高明的手段,只能随便猜一个。然后,A 向 B 揭晓答案,并告诉 B 他刚才选了哪几个素数,让 B 验证答案的真实性。
理论上说,这种做法是绝对公平而随机的,不过过程却太麻烦了一些,在现实生活中没法普及。不过,在信息世界中,类似的方案已经得到了广泛的应用。利用计算机,我们可以得到几十上百位的素数,并能迅速算出这些大素数的乘积,但要想把乘积分解开来几乎是一件不可能完成的任务。可以说,大素数分解不但是电子抛币协议的理论依据,也是消息加密、电子签名、身份验证等一切信息安全的根基。在人们为信息通讯的各种麻烦事儿而头疼时,古老的数论重新绽放光彩,这可以说是数学与科技的又一次漂亮的结合。