当你穿越到道诡异仙的世界,如何利用密码学知识区分幻想和现实?
《道诡异仙》是一部流行的网络小说。
其中,剧情讲述了男主角李火旺穿越到诡异世界,但意识时不时会回到原来的现代社会中。两个世界时不时交错,男主角陷入到了混乱当中,一直在疑惑到底哪边世界是真实的,也因此发展出了精彩的故事。
那么,作为一个程序员,如果面临这样的处境,有没有办法利用专业知识区分世界是否是真实的呢?
其实不论什么样的异世界,数学始终不变,我们可以利用密码学背后的数学原理,来检查一个世界是否是真实世界。
在剧情中,男主角李火旺一直怀疑他所处的“现代世界”是幻觉,那么,我们很容易想到,幻觉没办法伪造算力,只要我们构造一个需要一定算力的数学问题,再交给“现代世界”的女主角杨娜去找计算机计算就可以了。
但是考虑到书中"诡异世界"并没有关于计算的神通,其数学发展水平也有限,所以我们构造出的问题应该是难以计算,但是又易于检验的。这样的问题与密码学所需的数学原理非常相似,我们可以利用一个简单的事实:
计算两个大质数的乘积非常简单,但是把两个大质数的乘积质因数分解却非常困难。
所以我们可以设计这样一个方案:
- 首先教会"诡异世界”一侧的女主角白灵淼学会基本算术(只要到整数乘法就可以了)。接下来,指挥白灵淼生成两个大质数,并且把它们的乘积告诉男主。
- 待男主穿越回“现代世界”,把这个乘积告诉"现代世界"女主角杨娜,请她去找计算机计算它的质因数分解,之后再告诉男主。
- 男主回到诡异世界,检查"现代世界"给出的质因数分解结果是否正确,如果正确,那么"现代世界"必定是真实的。
那么,如何在基础算术之内,生成较大的质数呢?我们可以利用费马小定理:
如果p是一个质数,而整数a不是p的倍数,则a^(p-1) 除以p余1 。
实际上,取a为偶数,ap−1×p+1a^{p-1} \times p+1ap−1×p+1在多数情况下都是质数。在不那么严格的情况下,我们完全可以把这些伪质数当作质数来使用。
针对验证世界是否存在算力的场景,我们只需要选择两个大约几十万的整数就可以了,比如:
6^{7-1} * 7+1 = 326593125−1∗5+1=10368167−1∗7+1=326593
如果怕踩到坑,可以拿一些小质数试验一下。
之后我们计算它们的乘积,得到了 338614888333386148883333861488833
这些计算量稍微有点大,但是应该还在小白的能力范围内,最多花上一个小时,足够完成计算了。
注意,为了防止幻觉作弊,小白只告诉李火旺最终的乘积,不需要告诉李火旺两个质因数。
接下来,让我们的主角回到"现代世界",把338614888333386148883333861488833交给"现代世界"女主角杨娜,要求她找计算机和程序员对33861488833做因式分解。
接下来杨娜大约要花一点钱,比如她找到了winter,因式分解的代码这样写:
let p = new Array(Math.ceil(Math.sqrt(33861488833))).fill(1)
p[0] = 0;
p[1] = 0;
for(let i = 2; i < p.length; i++) {
if(i === 0)
continue;
if(33861488833 % i === 0)
console.log(i);
for(let j = i * 2; j < p.length; j += i)
p[j] = 0;
}
//运行结果:103681
用计算机计算这个循环只需要几秒,但是如果是人肉计算,这个工作量几乎是不可完成的。
幻觉再怎么厉害,也不可能帮助李火旺超越数学,算出这个因式分解的结果。
如果在"现代世界"中,算出了正确的因式分解结果,因为李火旺本人并不知道质因数,所以可以确定不可能是李火旺的幻觉。
这样就可以验证"现代世界"的真实性了。
换句话说,即使"现代世界"是幻觉,那也是一个有巨大算力的幻觉系统,那么《道诡异仙》的故事可能就变成另一种风格了。
来源:juejin.cn/post/7250718023815528485