两个人如何通过电话「扔硬币」？ 第1页

在数学中，有一个非常典型的“正则易、逆则难”的现象：那就是很容易算出两个素数的乘积是多少，却没法快速找出一个大数能够分解为哪些素数的乘积。

首先介绍一下“合数”和“素数”。有些数能够成更小的数的乘积形式，比如 8 可以写成 2×4，35 可以写成5×7，这样的数就被称为“合数”。

而另一些数则比较特殊，并不能写成更小的数的乘积，而只能被1或自己本身整除，比如2、3、5、 7、23、67、191 等等，这样的数就叫做“素数”。

如果我们选取两个素数，比方说67和71，然后把它们相乘，得到新的数4757，这一步并不困难。但是反过来，除非我们一个数一个数地去遍历尝试，否则是没办法判断出4757可以分成哪两个素数的乘积形式。换句话说，对于“4757能分成哪两个数的乘积”这个问题，回答起来相当困难，验证答案的正确性却相对容易的多。从计算复杂度的角度很容易理解，把67和71相乘的复杂度为O(1)，而现有的Pollard Rho快速因数分解算法的复杂度为O(n^(1/4))。

利用上述思路，可以到很多公平的电话抛币方案。比如：

我们规定由A 先抛一枚硬币，如果硬币为正面朝上，A就选择两个 1000 左右的素数；否则就选择三个 100 左右的素数。然后 A 把所选的素数乘起来，只把乘积告诉B，并让B回答这个乘积是两个数的乘积还是三个数的乘积。因为对于普通人而言，这个计算量绝对是难以达到的，所以B只能随机猜一个，并把猜的结果告知A。最后，A向B揭晓答案，并将自己刚才所选的素数告知B，让B验证答案的真实性。用一句话描述核心思想就是A不能捏造，B不能破解。

举个例子，我告诉大家一个素数乘积结果1011811，大家能否在不借助计算机的情况下，通过心算在10秒内告诉我答案呢？

即使有人说，B完全可以作弊，比如他直接借助计算机来分解乘积。不过，若A怀疑B会通过计算机作弊，A完全可以设定各大的乘积位数，例如1000000000000位的素数乘积，即使是超级计算机也没办法在10秒内完成。

理论上说，这种电话抛硬币方案是公平可靠的，但是其执行过程却有点太麻烦，所以在实际中应该不会有人这么做。然而，这种思想在计算机科学中已经得到了广泛应用。利用计算机，我们可以轻松得到几十上百位的素数，并能迅速算出这些大素数的乘积，但要想把乘积快速分解开来是一件几乎不可能完成的任务。

值得一提的是，这也是当今最有影响力的公钥加密算法——RSA算法的原理，利用该算法可以快速对文件进行加密，但是暴力解密却需要花费很长的时间。

【文献】果壳网：两个人能在电话中抛掷硬币吗？