在数学中,有一个非常典型的“正则易、逆则难”的现象:那就是很容易算出两个素数的乘积是多少,却没法快速找出一个大数能够分解为哪些素数的乘积。
首先介绍一下“合数”和“素数”。有些数能够成更小的数的乘积形式,比如 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算法的原理,利用该算法可以快速对文件进行加密,但是暴力解密却需要花费很长的时间。
【文献】果壳网:两个人能在电话中抛掷硬币吗?
本站所有内容均为互联网搜索引擎提供的公开搜索信息,本站不存储任何数据与内容,任何内容与数据均与本站无关,如有需要请联系相关搜索引擎包括但不限于百度,google,bing,sogou 等
© 2025 tinynews.org All Rights Reserved. 百科问答小站 版权所有